Submission #3236622

---

Source Code Expand

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

using namespace std;

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;

#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))

int F()
{
	char ch;
	int x, a;
	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
	if (ch == '-') ch = getchar(), a = -1;
	else a = 1;
	x = ch - '0';
	while (ch = getchar(), ch >= '0' && ch <= '9')
		x = (x << 1) + (x << 3) + ch - '0';
	return a * x;
}

const int mod = 1e9 + 7;

const int N = 2e5 + 10;

int n;

PII t[N];

int id[N];

int L[N], R[N];

VI q[N];

bool comp(const int &i, const int &j)
{
	return t[i].se < t[j].se;
}

int tr[N];

void add(int x, int v)
{
	++x;
	for (; x < N; x += x & -x) (tr[x] += v) %= mod;
}

int sum(int x)
{
	++x;
	int v = 0;
	for (; x; x -= x & -x) (v += tr[x]) %= mod;
	return v;
}

int query(int l, int r)
{
	return (sum(r) - sum(l - 1) + mod) % mod;
}

int main()
{
	gi(n);
	for (int i = 1; i <= n; ++i)
		gii(t[i].se, t[i].fi), id[i] = i;
	sort(t + 1, t + n + 1);
	sort(id + 1, id + n + 1, comp);
	int mi = n, mx = 0;
	for (int i = n; i; --i)
	{
		mi = min(mi, id[i]);
		L[i] = mi;
	}
	for (int i = 1; i <= n; ++i)
	{
		mx = max(mx, id[i]);
		R[i] = mx;
		q[R[i]].pb(L[i]);
		//cerr << L[i] << ", " << R[i] << endl;
	}
	add(0, 1);
	for (int r = 1; r <= n; ++r)
		for (auto l : q[r])
			add(r, query(l - 1, r));
	printf("%d\n", query(n, n));
	return 0;
}

Submission Info

Judge Result