Submission #1389389

---

Source Code Expand

import java.util.Arrays;
import java.util.Scanner;

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

	void run() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] s = new int[n];
		int[] t = new int[n];
		int sz = 1_000_00;
		SegmentTree st = new SegmentTree(sz);
		for (int i = 0; i < n; ++i) {
			s[i] = sc.nextInt();
			t[i] = sc.nextInt();
			--s[i];
			--t[i];
			st.add(s[i], t[i], 1);
		}
		int ans = Integer.MAX_VALUE;
		for (int i = 0; i < n; ++i) {
			st.add(s[i], t[i], -1);
			ans = Math.min(ans, st.query(0, sz));
			st.add(s[i], t[i], 1);
		}
		System.out.println(ans);

	}

	class SegmentTree {
		int n = 1;
		int[] v;
		int[] lazy;

		public SegmentTree(int n_) {
			while (n < n_) {
				n *= 2;
			}
			v = new int[2 * n - 1];
			lazy = new int[2 * n - 1];
			Arrays.fill(v, 0);
		}

		void push(int k) {
			if (lazy[k] == 0) {
				return;
			}
			if (k < n - 1) {
				lazy[2 * k + 1] += lazy[k];
				lazy[2 * k + 2] += lazy[k];
			}
			v[k] += lazy[k];
			lazy[k] = 0;
		}

		int add(int a, int b, int add) {
			return query(a, b, 0, n, 0, add);
		}

		int query(int a, int b) {
			return query(a, b, 0, n, 0, 0);
		}

		// [a,b)
		// [l,r)
		int query(int a, int b, int l, int r, int k, int add) {
			push(k);
			if (a <= l && r <= b) {
				lazy[k] = add;
				push(k);
				return v[k];
			} else if (b <= l || r <= a) {
				return 0;
			} else {
				int vl = query(a, b, l, (l + r) / 2, 2 * k + 1, add);
				int vr = query(a, b, (l + r) / 2, r, 2 * k + 2, add);
				v[k] = Math.max(v[2 * k + 1], v[2 * k + 2]);
				return Math.max(vl, vr);
			}
		}

	}

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

Submission Info

Judge Result