Submission #1318194
Source Code Expand
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
int mod = 1000000007;
int add(int x, int y) { return (x += y) >= mod ? x - mod : x; }
template<class... T> int add(int x, T... y) { return add(x, add(y...)); }
int mul(int x, int y) { return 1LL * x * y % mod; }
template<class... T> int mul(int x, T... y) { return mul(x, mul(y...)); }
int sub(int x, int y) { return add(x, mod - y); }
int modpow(int a, long long b) {
int ret = 1; while (b > 0) {
if (b & 1) ret = 1LL * ret * a % mod; a = 1LL * a * a % mod; b >>= 1;
} return ret;
}
int modinv(int a) { return modpow(a, mod - 2); }
#define def 0
template<class V, int NV> struct SegTree {
V comp(V l, V r) { return add(l,r); };
vector<V> val; SegTree() { val = vector<V>(NV * 2, def); }
V get(int l, int r) { //[l,r]
if (l > r) return def;
l += NV; r += NV + 1; V ret = def;
while (l < r) { if (l & 1) ret = comp(ret, val[l++]); if (r & 1) ret = comp(ret, val[--r]); l /= 2; r /= 2; }
return ret;
}
V get(int x) { return val[x + NV]; }
void update(int i, V v) { i += NV; val[i] = v; while (i>1) i >>= 1, val[i] = comp(val[i * 2], val[i * 2 + 1]); }
};
/*---------------------------------------------------------------------------------------------------
∧_∧
∧_∧ (´<_` ) Welcome to My Coding Space!
( ´_ゝ`) / ⌒i
/ \ | |
/ / ̄ ̄ ̄ ̄/ |
__(__ニつ/ _/ .| .|____
\/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/
int N;
pair<int, int> P[201010];
//---------------------------------------------------------------------------------------------------
void zaatsu() {
vector<int> dic;
rep(i, 0, N) dic.push_back(P[i].second);
sort(dic.begin(), dic.end());
dic.erase(unique(dic.begin(), dic.end()), dic.end());
rep(i, 0, N) P[i].second = lower_bound(dic.begin(), dic.end(), P[i].second) - dic.begin() + 1;
/*rep(i, 0, N) printf("%d %d\n", L[i], R[i]);
printf("<%d>\n", M);*/
}
//---------------------------------------------------------------------------------------------------
#define INF INT_MAX/2
#define rrep(i,a,b) for(int i=a;i>=b;i--)
int L[201010], R[201010];
void change() {
sort(P, P + N);
rep(i, 0, N) {
int pre = 0;
if (0 < i) pre = R[i - 1];
R[i] = max(pre, P[i].second);
}
L[N] = INF;
rrep(i, N - 1, 0) {
int pre = L[i + 1];
L[i] = min(pre, P[i].second);
}
//rep(i, 0, N) printf("%d %d\n", L[i], R[i]);
}
//---------------------------------------------------------------------------------------------------
// Solution1 O(N^2)
/*int dp[2020][2020];
int dodp() {
dp[0][0] = 1;
rep(i, 0, N) {
rep(j, 0, M + 1) dp[i + 1][j] = dp[i][j];
int sm = 0;
rep(j, L[i] - 1, R[i] + 1) sm = add(sm, dp[i][j]);
dp[i + 1][R[i]] = add(dp[i + 1][R[i]], sm);
}
return dp[N][N];
}*/
//---------------------------------------------------------------------------------------------------
// Solution2 O(N^2)
/*int dp[201010];
int dodp() {
dp[0] = 1;
rep(i, 0, N) {
int sm = 0;
rep(j, L[i] - 1, R[i] + 1) sm = add(sm, dp[j]);
dp[R[i]] = add(dp[R[i]], sm);
}
return dp[N];
}*/
//---------------------------------------------------------------------------------------------------
// Solution3 O(NlogN)
/*SegTree<int, 1 << 18> dp;
int dodp() {
dp.update(0, 1);
rep(i, 0, N) {
int sm = dp.get(L[i] - 1, R[i]);
dp.update(R[i], add(dp.get(R[i]), sm));
}
return dp.get(N);
}*/
//---------------------------------------------------------------------------------------------------
// Solution4 O(N)
int dp[201010];
int sm[201010];
int dodp() {
dp[0] = 1;
sm[0] = 1;
int r = 0;
rep(i, 0, N) {
while (r < R[i] - 1) {
r++;
sm[r] = add(sm[r - 1], dp[r]);
}
int s = sm[R[i] - 1];
if (0 <= L[i] - 2) s = sub(s, sm[L[i] - 2]);
s = add(s, dp[R[i]]);
dp[R[i]] = add(dp[R[i]], s);
}
return dp[N];
}
//---------------------------------------------------------------------------------------------------
void _main() {
cin >> N;
rep(i, 0, N) cin >> P[i].first >> P[i].second;
zaatsu();
change();
cout << dodp() << endl;
}
Submission Info
Submission Time |
|
Task |
E - Mr.Aoki Incubator |
User |
hamayanhamayan |
Language |
C++14 (GCC 5.4.1) |
Score |
1200 |
Code Size |
4921 Byte |
Status |
AC |
Exec Time |
98 ms |
Memory |
5092 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1200 / 1200 |
Status |
|
|
Set Name |
Test Cases |
Sample |
s1.txt, s2.txt |
All |
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, s1.txt, s2.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
AC |
84 ms |
4324 KB |
02.txt |
AC |
86 ms |
4324 KB |
03.txt |
AC |
96 ms |
4324 KB |
04.txt |
AC |
84 ms |
4324 KB |
05.txt |
AC |
84 ms |
4324 KB |
06.txt |
AC |
95 ms |
4324 KB |
07.txt |
AC |
84 ms |
4324 KB |
08.txt |
AC |
85 ms |
4324 KB |
09.txt |
AC |
97 ms |
5092 KB |
10.txt |
AC |
59 ms |
4324 KB |
11.txt |
AC |
61 ms |
5092 KB |
12.txt |
AC |
97 ms |
5092 KB |
13.txt |
AC |
60 ms |
5092 KB |
14.txt |
AC |
61 ms |
5092 KB |
15.txt |
AC |
97 ms |
5092 KB |
16.txt |
AC |
59 ms |
5092 KB |
17.txt |
AC |
61 ms |
5092 KB |
18.txt |
AC |
97 ms |
5092 KB |
19.txt |
AC |
59 ms |
5092 KB |
20.txt |
AC |
61 ms |
5092 KB |
21.txt |
AC |
97 ms |
5092 KB |
22.txt |
AC |
62 ms |
5092 KB |
23.txt |
AC |
63 ms |
5092 KB |
24.txt |
AC |
97 ms |
5092 KB |
25.txt |
AC |
61 ms |
4452 KB |
26.txt |
AC |
60 ms |
4452 KB |
27.txt |
AC |
95 ms |
4452 KB |
28.txt |
AC |
60 ms |
4452 KB |
29.txt |
AC |
61 ms |
4708 KB |
30.txt |
AC |
98 ms |
4836 KB |
31.txt |
AC |
2 ms |
2304 KB |
32.txt |
AC |
2 ms |
2304 KB |
33.txt |
AC |
2 ms |
2304 KB |
34.txt |
AC |
2 ms |
2304 KB |
s1.txt |
AC |
2 ms |
2304 KB |
s2.txt |
AC |
2 ms |
2304 KB |