Submission #1840503

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#define rep(i, a, b) for (int i = (a), _ = (b); i <= _; ++ i)
#define per(i, a, b) for (int i = (a), _ = (b); i >= _; -- i)
#define For(i, a, b) for (int i = (a), _ = (b); i < _; ++ i)
#define ri rd<int>
using namespace std;
const int maxN = 2e5 + 7;

template<class T> inline T rd() {
	bool f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = 0;
	T x = 0; for (; isdigit(c); c = getchar()) x = x * 10 + c - 48; return f ? x : -x;
}

int n, m;

struct rec {
	int x, y;
	inline bool operator < (const rec &v) {
		return (x == v.x) ? y > v.y : x < v.x;
	}
}a[maxN];

namespace Seg {
	static const int maxN = 524297;
	#define lc (x << 1)
	#define rc (x << 1 | 1)

	int mx[maxN], tag[maxN];

	void pushup(int x) {
		mx[x] = max(mx[lc], mx[rc]);
	}

	void totag(int x, int d) {
		mx[x] += d; tag[x] += d;
	}

	void pushdown(int x) {
		if (tag[x]) {
			totag(lc, tag[x]);
			totag(rc, tag[x]);
			tag[x] = 0;
		}
	}

	void build(int x, int l, int r) {
		tag[x] = 0;
		if (l == r) {
			mx[x] = l;
			return;
		}
		int mid = (l + r) >> 1;
		build(lc, l, mid);
		build(rc, mid+1, r);
		pushup(x);
	}

	void add(int x, int l, int r, int tl, int tr) {
		if (tl <= l && r <= tr) {totag(x, 1); return;}
		int mid = (l + r) >> 1;
		pushdown(x);
		if (tl <= mid) add(lc, l, mid, tl, tr);
		if (mid < tr) add(rc, mid+1, r, tl, tr);
		pushup(x);
	}

	int get(int x, int l, int r, int tl, int tr) {
		if (tl <= l && r <= tr) return mx[x];
		int mid = (l + r) >> 1;
		pushdown(x);
		if (tr <= mid) return get(lc, l, mid, tl, tr);
		if (mid < tl) return get(rc, mid+1, r, tl, tr);
		return max(get(lc, l, mid, tl, tr), get(rc, mid+1, r, tl, tr));
	}

	inline void build() {build(1, 0, m+1);}
	inline void add(int l, int r) {add(1, 0, m+1, l, r);}
	inline int get(int l, int r) {return get(1, 0, m+1, l, r);}

	#undef lc
	#undef rc
}

int main() {

	n = ri(), m = ri();
	rep (i, 1, n) a[i].x = ri(), a[i].y = ri();
	sort(a+1, a+n+1);
	
	int res = max(n - m, 0);
	Seg::build();
	rep (i, 1, n) {
		Seg::add(1, a[i].y);
		if (a[i].x <= m) res = max(res, Seg::get(a[i].x + 1, m + 1) - a[i].x - (m + 1));
	}
	printf("%d\n", res);

	return 0;
}

Submission Info

Judge Result