Submission #941524

---

Source Code Expand

import java.io.PrintWriter;
import java.util.*;

public class Main {
	public static void main(String[] args) {
		new Main().run();
	}

	void run() {
		solver();
	}

	void solver() {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		int n = sc.nextInt();
		int L = sc.nextInt();
		int[] t = new int[n];
		int[] p = new int[n];
		for (int i = 0; i < n; i++) {
			t[i] = sc.nextInt();
			p[i] = sc.nextInt();
		}

		PriorityQueue<Long> pq = new PriorityQueue<>();
		int mid = 0;
		long ret = 0;
		for (int i = 0; i < n;) {
			int j = i;
			while (j < n && t[i] == t[j]) {
				++j;
			}
			for (int k = i; k < j; ++k) {
				pq.add(-((long) p[k] << 32 | k));
				pq.add(-((long) p[k] << 32 | k));
			}
			long c = 0;
			while (pq.size() > j) {
				long polled = -pq.poll();
				if ((int) polled < i && mid >= (polled >>> 32)) {
					++c;
				}
				long next = -pq.peek();
				if (next >>> 32 <= mid) {
					ret += (mid - (next >>> 32)) * c;
					mid = (int) (next >>> 32);
				}
			}
			mid = (int) ((-pq.peek()) >>> 32);
			for (int k = i; k < j; ++k) {
				ret += Math.abs(p[k] - mid);
			}
			i = j;
		}
		pw.println(ret);
		pw.close();
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}

Submission Info

Judge Result