C++

There's multiple ways we can do this. The most straightforward method is to use a pair<int, pair<int, int>>. When comparing these, C++ looks at the first element and only uses the second element as a tiebreaker.

Copy
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
	constexpr int edge_num = 4;

	vector<pair<int, pair<int, int>>> edges(edge_num);

If you don't like all the accesses to .first and .second, an alternative is to use an std::vector or maybe even an std::array:

Copy
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
	constexpr int edge_num = 4;

	// array<int, 3> is also usable and probably faster

Java

Unfortunately, Java doesn't have much builtin support for sorting collections of multiple elements; it mostly limits us to sorting raw integer arrays and the like.

To implement sorting by custom values in Java, we need to utilize comparators, which will be covered below.

Python

There's multiple ways we can do this. In Python, we can use a list of lists:

Copy
edge_num = 4

edges = []
for _ in range(edge_num):
	a, b, width = [int(i) for i in input().split()]
	edges.append((width, a, b))
edges.sort()

for e in edges:
	print(f"({e[1]}, {e[2]}): {e[0]}")

Another option would be a Tuple[int, Tuple[int]], but that would make indexing more convoluted.

C++

In C++, its comparators must obey a set of behaviors. Let's call this comparator compare, and the objects it compares x and y.

• If x is less than y, return true.
• If y is greater than or equal to y, return false.
• If compare(x, y) is true, then compare(y, x) must be false. (antisymmetry)
• If compare(x, y) is true and compare(y, z) is true, then compare(x, z) must be true. (transitivity)

Essentially, the comparator determines whether $x$ belongs to the left of $y$ in a sorted ordering.

Overloading operator<

This is the easiest to implement. However, it only works for objects (not primitives) and it doesn't allow you to define multiple ways to compare the same type of class.

Let's sort those four edges again with this new method:

Copy
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

struct Edge {
	int a, b;
	int width;

It's also possible to define operator< outside of the class:

Copy
struct Edge {
	int a, b;
	int width;
};

bool operator<(const Edge &x, const Edge &y) { return x.width < y.width; }

Comparison Function

We can also pass the comparator as a lambda directly into std::sort. This has the advantage of working with primitives as well as classes.

Copy
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

struct Edge {
	int a, b;
	int width;
};

Java

In Java, its comparators must obey a set of behaviors. Let's call this comparator compare, and the objects it compares x and y. For compare to be valid, the following must be true:

• If x is less than y, return -1.
• If y is greater than y, return 1.
• If the two are equal, return 0.
• If compare(x, y) > 0, then compare(y, x) < 0. (antisymmetry)
• If compare(x, y) > 0 and compare(y, z) > 0, then compare(x, z) > 0. (transitivity)

Essentially, the comparator determines whether $x$ belongs to the left of $y$ in a sorted ordering.

Java has some builtin comparables such as Integer.compare and Arrays.compare, but we often find ourselves having to define our own.

Implementing Comparable<T>

To make a class T sortable, we have to make it extend Comparable<T>. After that, we also have to implement the compareTo method which takes an instance of another class and returns a number according to the rules described above.

When using Comparable, we can call Arrays.sort(arr) or Collections.sort(list) on the array or list as usual.

Copy
import java.util.*;

class Edge implements Comparable<Edge> {
	public int a, b;
	public int width;

	public Edge(int a, int b, int width) {
		this.a = a;
		this.b = b;
		this.width = width;

Comparator Fucntion

We can also pass a comparator function directly to Arrays.sort (or Collections.sort, if you're sorting an ArrayList).

Copy
import java.io.*;

class Edge {
	public int a, b;
	public int width;

	public Edge(int a, int b, int width) {
		this.a = a;
		this.b = b;
		this.width = width;

Python

Key Function

Python's sorting functions take a key argument that takes in an object and returns a comparable datatype like an int.

Copy
class Edge:
	def __init__(self, a: int, b: int, width: int):
		self.a = a
		self.b = b
		self.width = width


edge_num = 4
edges = [Edge(*[int(i) for i in input().split()]) for _ in range(edge_num)]
edges.sort(key=lambda e: e.width)

for e in edges:
	print(f"({e.a}, {e.b}): {e.width}")

Comparator

A less idiomatic but still supported way to sort objects in Python is with comparators that return the relative order of two objects.

Let's call this comparator compare, and the objects it compares x and y. For compare to be valid, the following must be true:

• If x is less than y, return -1.
• If y is greater than y, return 1.
• If the two are equal, return 0.
• If compare(x, y) > 0, then compare(y, x) < 0. (antisymmetry)
• If compare(x, y) > 0 and compare(y, z) > 0, then compare(x, z) > 0. (transitivity)

Python's sorting functions don't take comparators directly. We have to convert them to something key can take with functools.cmp_to_key like so:

Copy
from functools import cmp_to_key


class Edge:
	def __init__(self, a: int, b: int, width: int):
		self.a = a
		self.b = b
		self.width = width

See this SO post for an explanation of how cmp_to_key works.

C++

Copy
struct Edge {
	int a, b;
	int width;

	bool operator<(const Edge &y) {
		if (width == y.width) { return width < y.width; }
		return a < y.a;
	}
};

Java

Copy
class Edge implements Comparable<Edge> {
	public int a, b;
	public int width;

	public Edge(int a, int b, int width) {
		this.a = a;
		this.b = b;
		this.width = width;
	}

Python

In Python, tuples have a natural order based on their elements in order. We can take advantage of this to write a comparator:

Copy
edges.sort(key=lambda edge: (edge.width, edge.a))

C++

Copy
#include <algorithm>
#include <iostream>

using namespace std;

typedef pair<int, int> Point;
bool ycomp(Point p, Point q) { return p.second < q.second; }

const int MAX_N = 2500;
int pref[MAX_N + 1][MAX_N + 1];

Java

Copy
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class RectangularPasture {
	static int[][] sums;

	static int getSum(int fromX, int toX, int fromY, int toY) {
		return sums[toX][toY] - sums[fromX - 1][toY] - sums[toX][fromY - 1] +
		    sums[fromX - 1][fromY - 1];

Python

Copy
import sys

input = sys.stdin.readline

n = int(input().strip())
points = [list(map(int, input().strip().split())) for _ in range(n)]

points.sort(key=lambda i: i[1])
for i in range(n):
	points[i][1] = i + 1

C++

Copy
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll difference_array[400005];
// difference_array[i] = the difference of the values between special intervals
// i-1 and i

Java

Copy
import java.io.*;
import java.util.*;

public class StaticRangeQueries {
	// custom class that stores a few integers (used for directly storing the
	// queries and updates given in the input)
	static class Query {
		int l, r, v;
		public Query(int l, int r, int v) {
			this.l = l;