Submission #2232830

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SIZE(a) ((int)(a).size())

const int N = 200005;

const int mod = 1000*1000*1000 + 7;

int n;
pair<int,int> a[N];
int lf[N], rt[N];
int seg[N];
int f[N];

inline void add(int &x, int y) {
	x += y;
	if (x >= mod) x -= mod;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	REP(i, n) cin >> a[i].first >> a[i].second;
	REP(i, n+2) seg[i] = -1;
	sort(a, a + n);

	vector<pair<int,int>> b(n);
	REP(i, n) b[i] = {a[i].second, i};
	sort(b.begin(), b.end());

	int mx = -1;
	REP(i, n) {
		mx = max(mx, b[i].second);
		rt[b[i].second] = mx+1;
	}
	int mn = n;
	for (int i = n-1; i >= 0; --i) {
		mn = min(mn, b[i].second);
		lf[b[i].second] = mn+1;
	}

	REP(i, n) {
		seg[rt[i]] = max(seg[rt[i]], lf[i]);
	}

	int sum = 1;
	f[0] = 1;

	mx = -1;
	int j = 0;

	for (int i = 1; i <= n+1; ++i) {
		mx = max(mx, seg[i-1]);
		while (j < mx) {
			add(sum, mod-f[j]);
			++j;
		}
		add(f[i], sum);
		add(sum, sum);
	}

	cout << f[n+1] << '\n';

	return 0;
}

Submission Info

Judge Result