#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define pill pair<ll, ll>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
const int N = 5e5 + 10;
const int M = 5e5 + 10;
const int C = 1e7 + 1e5;
const ll mod = 1e9 + 7;
const ll hsh[2] = {1555555699, 1222222763};
ll n, m, k;
ll a[M], b[M];
ll A[N], B[N];
ll sz = 0, ans = 0;
ll as[N];
ll pdp[N][26];
ll dp[26];
ll sprs[N][19];
ll sprs2[N][19];
ll maxA(ll l, ll r) {
ll z = __lg(r - l + 1);
return max(sprs[l][z], sprs[r - (1<<z) + 1][z]);
}
ll maxB(ll l, ll r) {
ll z = __lg(r - l + 1);
return max(sprs2[l][z], sprs2[r - (1<<z) + 1][z]);
}
void build() {
for(int j = 1; j <= n; j++) {
sprs[j][0] = A[j];
sprs2[j][0] = B[j];
}
for(int i = 1; i < 19; i++) {
for(int j = 1; j <= n - (1<<i) + 1; j++) {
sprs[j][i] = max(sprs[j][i - 1], sprs[j + (1<<(i - 1))][i - 1]);
sprs2[j][i] = max(sprs2[j][i - 1], sprs2[j + (1<<(i - 1))][i - 1]);
}
}
}
int main() {
speed;
cin >> n >> m;
for(int i = 1; i <= m; i++) {
cin >> a[i] >> b[i];
if(a[i] < b[i])
A[a[i]] = max(b[i], A[a[i]]);
else
B[b[i]] = max(a[i], B[b[i]]);
}
build();
ll cnn = 0;
for(int i = 1; i <= n; i++) {
if(A[i])
cnn++, a[cnn] = i, b[cnn] = A[i];
if(B[i])
cnn++, a[cnn] = B[i], b[cnn] = i;
}
m = cnn;
for(int j = 0; j < 26; j++)
pdp[1][j] = j + 1;
for(int i = 2; i <= n; i++) {
// <
ll l = 1, r = i - 1, ans = i;
while(l <= r) {
ll m = (l + r) >> 1ll;
if(maxA(m, i - 1) < i)
r = m - 1, ans = m;
else
l = m + 1;
}
if(ans < i) {
for(int k = 1; k < 26; k++) {
dp[k] = (dp[k] + pdp[i - 1][k - 1] - pdp[ans - 1][k - 1] + mod) % mod;
}
}
// >
l = 1, r = i - 1, ans = i;
while(l <= r) {
ll m = (l + r) >> 1ll;
if(maxB(m, i - 1) < i)
r = m - 1, ans = m;
else
l = m + 1;
}
if(ans < i) {
for(int k = 0; k < 26; k++) {
dp[k] = (dp[k] + (pdp[i - 1][25] - pdp[ans - 1][25] - pdp[i - 1][k] + pdp[ans - 1][k]) + 3ll * mod) % mod;
}
}
for(int j = 0; j < 26; j++) {
pdp[i][j] = (dp[j] + pdp[i - 1][j]) % mod;
if(j < 25) dp[j + 1] = (dp[j + 1] + dp[j]) % mod;
dp[j] = 0;
}
}
cout << pdp[n][25];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
328 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
328 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
328 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
328 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
456 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
1 ms |
468 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
1 ms |
468 KB |
Output is correct |
21 |
Correct |
1 ms |
456 KB |
Output is correct |
22 |
Correct |
2 ms |
576 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
468 KB |
Output is correct |
25 |
Correct |
1 ms |
456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
324 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
328 KB |
Output is correct |
5 |
Correct |
737 ms |
272956 KB |
Output is correct |
6 |
Correct |
672 ms |
272968 KB |
Output is correct |
7 |
Correct |
685 ms |
272960 KB |
Output is correct |
8 |
Correct |
763 ms |
272944 KB |
Output is correct |
9 |
Correct |
687 ms |
272980 KB |
Output is correct |
10 |
Correct |
17 ms |
11228 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
756 ms |
272948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
328 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
328 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
456 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
1 ms |
468 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
1 ms |
468 KB |
Output is correct |
21 |
Correct |
1 ms |
456 KB |
Output is correct |
22 |
Correct |
2 ms |
576 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
468 KB |
Output is correct |
25 |
Correct |
1 ms |
456 KB |
Output is correct |
26 |
Correct |
16 ms |
11164 KB |
Output is correct |
27 |
Correct |
15 ms |
10712 KB |
Output is correct |
28 |
Correct |
15 ms |
10716 KB |
Output is correct |
29 |
Correct |
17 ms |
11184 KB |
Output is correct |
30 |
Correct |
17 ms |
11172 KB |
Output is correct |
31 |
Correct |
92 ms |
23740 KB |
Output is correct |
32 |
Correct |
18 ms |
11216 KB |
Output is correct |
33 |
Correct |
16 ms |
11220 KB |
Output is correct |
34 |
Correct |
17 ms |
11184 KB |
Output is correct |
35 |
Correct |
90 ms |
23740 KB |
Output is correct |
36 |
Correct |
13 ms |
10324 KB |
Output is correct |
37 |
Correct |
16 ms |
10956 KB |
Output is correct |
38 |
Correct |
15 ms |
10964 KB |
Output is correct |
39 |
Correct |
15 ms |
10800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
328 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
328 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
456 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
1 ms |
468 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
1 ms |
468 KB |
Output is correct |
21 |
Correct |
1 ms |
456 KB |
Output is correct |
22 |
Correct |
2 ms |
576 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
468 KB |
Output is correct |
25 |
Correct |
1 ms |
456 KB |
Output is correct |
26 |
Correct |
1 ms |
324 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
0 ms |
328 KB |
Output is correct |
30 |
Correct |
737 ms |
272956 KB |
Output is correct |
31 |
Correct |
672 ms |
272968 KB |
Output is correct |
32 |
Correct |
685 ms |
272960 KB |
Output is correct |
33 |
Correct |
763 ms |
272944 KB |
Output is correct |
34 |
Correct |
687 ms |
272980 KB |
Output is correct |
35 |
Correct |
17 ms |
11228 KB |
Output is correct |
36 |
Correct |
1 ms |
468 KB |
Output is correct |
37 |
Correct |
0 ms |
340 KB |
Output is correct |
38 |
Correct |
756 ms |
272948 KB |
Output is correct |
39 |
Correct |
16 ms |
11164 KB |
Output is correct |
40 |
Correct |
15 ms |
10712 KB |
Output is correct |
41 |
Correct |
15 ms |
10716 KB |
Output is correct |
42 |
Correct |
17 ms |
11184 KB |
Output is correct |
43 |
Correct |
17 ms |
11172 KB |
Output is correct |
44 |
Correct |
92 ms |
23740 KB |
Output is correct |
45 |
Correct |
18 ms |
11216 KB |
Output is correct |
46 |
Correct |
16 ms |
11220 KB |
Output is correct |
47 |
Correct |
17 ms |
11184 KB |
Output is correct |
48 |
Correct |
90 ms |
23740 KB |
Output is correct |
49 |
Correct |
13 ms |
10324 KB |
Output is correct |
50 |
Correct |
16 ms |
10956 KB |
Output is correct |
51 |
Correct |
15 ms |
10964 KB |
Output is correct |
52 |
Correct |
15 ms |
10800 KB |
Output is correct |
53 |
Correct |
656 ms |
263120 KB |
Output is correct |
54 |
Correct |
591 ms |
261888 KB |
Output is correct |
55 |
Correct |
670 ms |
272884 KB |
Output is correct |
56 |
Correct |
750 ms |
272772 KB |
Output is correct |
57 |
Correct |
756 ms |
273004 KB |
Output is correct |
58 |
Correct |
682 ms |
273020 KB |
Output is correct |
59 |
Correct |
653 ms |
273096 KB |
Output is correct |
60 |
Correct |
776 ms |
273056 KB |
Output is correct |
61 |
Correct |
496 ms |
250832 KB |
Output is correct |
62 |
Correct |
750 ms |
269364 KB |
Output is correct |
63 |
Correct |
707 ms |
265764 KB |
Output is correct |
64 |
Correct |
696 ms |
262084 KB |
Output is correct |