Submission #38506361

---

Source Code Expand

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

namespace vbzIO{
	char ibuf[(1 << 20) + 1], *iS, *iT;
	#if ONLINE_JUDGE
	#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
	#else
	#define gh() getchar()
	#endif
	#define reg register
	inline int read () {
		reg char ch = gh();
		reg long long x = 0;
		reg char t = 0;
		while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
		while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
		return t ? -x : x;
	}
	inline void write(int x) {
		if (x < 0) {
			x = ~(x - 1);
			putchar('-');
		}
		if (x > 9)
			write(x / 10);
		putchar(x % 10 + '0');
	}
}

using vbzIO::read;
using vbzIO::write;

const int maxn = 2e5 + 200;
const int mod = 1e9 + 7;
struct node { int v, x, tx; } a[maxn];
int n, len, t[maxn], tmn[maxn], tmx[maxn], lp[maxn], rp[maxn], f[maxn], s[maxn];
vector<int> g[maxn];

#define lb(x) x & (-x)
void mdf1(int x, int y) { for (int i = x; i; i -= lb(i)) tmn[i] = min(tmn[i], y); }
void mdf2(int x, int y) { for (int i = x; i <= len; i += lb(i)) tmx[i] = max(tmx[i], y); }
int qry1(int x) { int res = len + 1; for (int i = x; i <= n; i += lb(i)) res = min(res, tmn[i]); return res; }
int qry2(int x) { int res = 0; for (int i = x; i; i -= lb(i)) res = max(res, tmx[i]); return res; }

int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		a[i].x = read(), a[i].v = read();
		t[++len] = a[i].x;
	}
	sort(t + 1, t + len + 1);
	len = unique(t + 1, t + len + 1) - t - 1;
	for (int i = 1; i <= n; i++) 
		a[i].tx = lower_bound(t + 1, t + len + 1, a[i].x) - t;
	sort(a + 1, a + n + 1, [](const node &x, const node &y) { return x.v < y.v; }); 
	memset(tmn, 0x3f, sizeof(tmn));
	for (int i = 1; i <= n; i++) 
		mdf1(a[i].tx, i), lp[i] = qry1(a[i].tx);
	for (int i = n; i; i--) 
		mdf2(a[i].tx, i), rp[i] = qry2(a[i].tx);
	for (int i = 1; i <= n; i++) g[rp[i]].push_back(lp[i]);
	for (int i = 1; i <= n; i++) sort(g[i].begin(), g[i].end());
	f[0] = s[0] = 1;
//	for (int i = 0; i <= n; i++) s[0] = 1;
	for (int i = 1; i <= n; i++) {
		s[i] = s[i - 1];
		for (int j : g[i]) 
			(f[i] += (s[i] - (j >= 2 ? s[j - 2] : 0) + mod) % mod) %= mod,
			s[i] = (s[i - 1] + f[i]) % mod;
	}
	write(f[n]);
	return 0;
}
/*
3
2 5
6 1
3 7
*/

Submission Info

Compile Error

./Main.cpp: In function ‘int vbzIO::read()’:
./Main.cpp:14:12: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   14 |   reg char ch = gh();
      |            ^~
./Main.cpp:15:17: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   15 |   reg long long x = 0;
      |                 ^
./Main.cpp:16:12: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   16 |   reg char t = 0;
      |            ^

Judge Result