#include "bits/stdc++.h"
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a)
#define ar array
#define all(v) (v).begin(), (v).end()
#define sz(v) static_cast<int>(v.size())
typedef vector<int> vi;
typedef long long ll;
const int N = 5e5, N_ = 1 << 19, MD = 1e9 + 7;
struct ST {
ar<int, 26> t[N_ * 2];
bool on[N_ * 2];
void bld(int k, int l, int r) {
fill(all(t[k]), 0);
on[k] = 1;
if (l < r) {
int m = (l + r) / 2;
bld(k << 1 | 0, l, m), bld(k << 1 | 1, m + 1, r);
}
}
void upd(int k, int l, int r, int i, ar<int, 26>& x) {
F0R(c, 26)
t[k][c] = (t[k][c] + x[c]) % MD;
if (l < r) {
int m = (l + r) / 2;
if (i <= m)
upd(k << 1 | 0, l, m, i, x);
else
upd(k << 1 | 1, m + 1, r, i, x);
}
}
void clr(int k, int l, int r, int ql, int qr) {
if (!on[k] || ql > r || qr < l) return;
if (ql <= l && qr >= r) {
if (l < r) {
int m = (l + r) / 2;
clr(k << 1 | 0, l, m, ql, qr);
clr(k << 1 | 1, m + 1, r, ql, qr);
}
fill(all(t[k]), 0);
on[k] = 0;
return;
}
int m = (l + r) / 2;
clr(k << 1 | 0, l, m, ql, qr);
clr(k << 1 | 1, m + 1, r, ql, qr);
F0R(c, 26) t[k][c] = (t[k << 1 | 0][c] + t[k << 1 | 1][c]) % MD;
}
ar<int, 26>& root() { return t[1]; }
} t1, t2;
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin.exceptions(cin.failbit);
int n, m;
cin >> n >> m;
static vi v1[N], v2[N];
F0R(h, m) {
int l, r;
cin >> l >> r, l--, r--;
if (l < r)
v1[l].push_back(r); // s_i > s_{i+1}
else
v2[r].push_back(l); // s_i < s_{i+1}
}
t1.bld(1, 0, n - 1);
t2.bld(1, 0, n - 1);
ar<int, 26> dp;
R0F(i, n) {
if (i == n - 1)
fill(all(dp), 1);
else {
for (int j : v1[i]) t1.clr(1, 0, n - 1, i + 1, j);
for (int j : v2[i]) t2.clr(1, 0, n - 1, i + 1, j);
F0R(c, 26) {
dp[c] = 1;
FOR(b, 0, c) dp[c] = (dp[c] + t1.root()[b]) % MD;
FOR(b, c + 1, 26) dp[c] = (dp[c] + t2.root()[b]) % MD;
}
}
t1.upd(1, 0, n - 1, i, dp);
t2.upd(1, 0, n - 1, i, dp);
}
int ans = 0;
F0R(c, 26) ans = (ans + dp[c]) % MD;
cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
27996 KB |
Output is correct |
2 |
Correct |
7 ms |
27848 KB |
Output is correct |
3 |
Correct |
7 ms |
27996 KB |
Output is correct |
4 |
Correct |
7 ms |
27996 KB |
Output is correct |
5 |
Correct |
7 ms |
27996 KB |
Output is correct |
6 |
Correct |
7 ms |
27996 KB |
Output is correct |
7 |
Correct |
7 ms |
27996 KB |
Output is correct |
8 |
Correct |
7 ms |
27996 KB |
Output is correct |
9 |
Correct |
7 ms |
27996 KB |
Output is correct |
10 |
Correct |
8 ms |
28064 KB |
Output is correct |
11 |
Correct |
7 ms |
27996 KB |
Output is correct |
12 |
Correct |
7 ms |
27996 KB |
Output is correct |
13 |
Correct |
8 ms |
27852 KB |
Output is correct |
14 |
Correct |
7 ms |
27992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
27996 KB |
Output is correct |
2 |
Correct |
7 ms |
27848 KB |
Output is correct |
3 |
Correct |
7 ms |
27996 KB |
Output is correct |
4 |
Correct |
7 ms |
27996 KB |
Output is correct |
5 |
Correct |
7 ms |
27996 KB |
Output is correct |
6 |
Correct |
7 ms |
27996 KB |
Output is correct |
7 |
Correct |
7 ms |
27996 KB |
Output is correct |
8 |
Correct |
7 ms |
27996 KB |
Output is correct |
9 |
Correct |
7 ms |
27996 KB |
Output is correct |
10 |
Correct |
8 ms |
28064 KB |
Output is correct |
11 |
Correct |
7 ms |
27996 KB |
Output is correct |
12 |
Correct |
7 ms |
27996 KB |
Output is correct |
13 |
Correct |
8 ms |
27852 KB |
Output is correct |
14 |
Correct |
7 ms |
27992 KB |
Output is correct |
15 |
Correct |
8 ms |
27996 KB |
Output is correct |
16 |
Correct |
7 ms |
27996 KB |
Output is correct |
17 |
Correct |
7 ms |
27996 KB |
Output is correct |
18 |
Correct |
7 ms |
27996 KB |
Output is correct |
19 |
Correct |
8 ms |
27996 KB |
Output is correct |
20 |
Correct |
9 ms |
28124 KB |
Output is correct |
21 |
Correct |
7 ms |
27996 KB |
Output is correct |
22 |
Correct |
14 ms |
28252 KB |
Output is correct |
23 |
Correct |
7 ms |
27992 KB |
Output is correct |
24 |
Correct |
7 ms |
27996 KB |
Output is correct |
25 |
Correct |
8 ms |
27996 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
27996 KB |
Output is correct |
2 |
Correct |
7 ms |
27996 KB |
Output is correct |
3 |
Correct |
9 ms |
27996 KB |
Output is correct |
4 |
Correct |
7 ms |
27996 KB |
Output is correct |
5 |
Correct |
2171 ms |
261668 KB |
Output is correct |
6 |
Correct |
2193 ms |
261676 KB |
Output is correct |
7 |
Correct |
2336 ms |
261672 KB |
Output is correct |
8 |
Correct |
2208 ms |
261664 KB |
Output is correct |
9 |
Correct |
2180 ms |
261664 KB |
Output is correct |
10 |
Correct |
81 ms |
43468 KB |
Output is correct |
11 |
Correct |
9 ms |
28012 KB |
Output is correct |
12 |
Correct |
7 ms |
27996 KB |
Output is correct |
13 |
Correct |
2293 ms |
261664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
27996 KB |
Output is correct |
2 |
Correct |
7 ms |
27848 KB |
Output is correct |
3 |
Correct |
7 ms |
27996 KB |
Output is correct |
4 |
Correct |
7 ms |
27996 KB |
Output is correct |
5 |
Correct |
7 ms |
27996 KB |
Output is correct |
6 |
Correct |
7 ms |
27996 KB |
Output is correct |
7 |
Correct |
7 ms |
27996 KB |
Output is correct |
8 |
Correct |
7 ms |
27996 KB |
Output is correct |
9 |
Correct |
7 ms |
27996 KB |
Output is correct |
10 |
Correct |
8 ms |
28064 KB |
Output is correct |
11 |
Correct |
7 ms |
27996 KB |
Output is correct |
12 |
Correct |
7 ms |
27996 KB |
Output is correct |
13 |
Correct |
8 ms |
27852 KB |
Output is correct |
14 |
Correct |
7 ms |
27992 KB |
Output is correct |
15 |
Correct |
8 ms |
27996 KB |
Output is correct |
16 |
Correct |
7 ms |
27996 KB |
Output is correct |
17 |
Correct |
7 ms |
27996 KB |
Output is correct |
18 |
Correct |
7 ms |
27996 KB |
Output is correct |
19 |
Correct |
8 ms |
27996 KB |
Output is correct |
20 |
Correct |
9 ms |
28124 KB |
Output is correct |
21 |
Correct |
7 ms |
27996 KB |
Output is correct |
22 |
Correct |
14 ms |
28252 KB |
Output is correct |
23 |
Correct |
7 ms |
27992 KB |
Output is correct |
24 |
Correct |
7 ms |
27996 KB |
Output is correct |
25 |
Correct |
8 ms |
27996 KB |
Output is correct |
26 |
Correct |
98 ms |
43472 KB |
Output is correct |
27 |
Correct |
73 ms |
42992 KB |
Output is correct |
28 |
Correct |
76 ms |
42844 KB |
Output is correct |
29 |
Correct |
94 ms |
43352 KB |
Output is correct |
30 |
Correct |
94 ms |
43284 KB |
Output is correct |
31 |
Correct |
409 ms |
51644 KB |
Output is correct |
32 |
Correct |
84 ms |
43468 KB |
Output is correct |
33 |
Correct |
84 ms |
43484 KB |
Output is correct |
34 |
Correct |
95 ms |
43312 KB |
Output is correct |
35 |
Correct |
412 ms |
51916 KB |
Output is correct |
36 |
Correct |
69 ms |
42588 KB |
Output is correct |
37 |
Correct |
82 ms |
43160 KB |
Output is correct |
38 |
Correct |
78 ms |
42844 KB |
Output is correct |
39 |
Correct |
92 ms |
42844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
27996 KB |
Output is correct |
2 |
Correct |
7 ms |
27848 KB |
Output is correct |
3 |
Correct |
7 ms |
27996 KB |
Output is correct |
4 |
Correct |
7 ms |
27996 KB |
Output is correct |
5 |
Correct |
7 ms |
27996 KB |
Output is correct |
6 |
Correct |
7 ms |
27996 KB |
Output is correct |
7 |
Correct |
7 ms |
27996 KB |
Output is correct |
8 |
Correct |
7 ms |
27996 KB |
Output is correct |
9 |
Correct |
7 ms |
27996 KB |
Output is correct |
10 |
Correct |
8 ms |
28064 KB |
Output is correct |
11 |
Correct |
7 ms |
27996 KB |
Output is correct |
12 |
Correct |
7 ms |
27996 KB |
Output is correct |
13 |
Correct |
8 ms |
27852 KB |
Output is correct |
14 |
Correct |
7 ms |
27992 KB |
Output is correct |
15 |
Correct |
8 ms |
27996 KB |
Output is correct |
16 |
Correct |
7 ms |
27996 KB |
Output is correct |
17 |
Correct |
7 ms |
27996 KB |
Output is correct |
18 |
Correct |
7 ms |
27996 KB |
Output is correct |
19 |
Correct |
8 ms |
27996 KB |
Output is correct |
20 |
Correct |
9 ms |
28124 KB |
Output is correct |
21 |
Correct |
7 ms |
27996 KB |
Output is correct |
22 |
Correct |
14 ms |
28252 KB |
Output is correct |
23 |
Correct |
7 ms |
27992 KB |
Output is correct |
24 |
Correct |
7 ms |
27996 KB |
Output is correct |
25 |
Correct |
8 ms |
27996 KB |
Output is correct |
26 |
Correct |
7 ms |
27996 KB |
Output is correct |
27 |
Correct |
7 ms |
27996 KB |
Output is correct |
28 |
Correct |
9 ms |
27996 KB |
Output is correct |
29 |
Correct |
7 ms |
27996 KB |
Output is correct |
30 |
Correct |
2171 ms |
261668 KB |
Output is correct |
31 |
Correct |
2193 ms |
261676 KB |
Output is correct |
32 |
Correct |
2336 ms |
261672 KB |
Output is correct |
33 |
Correct |
2208 ms |
261664 KB |
Output is correct |
34 |
Correct |
2180 ms |
261664 KB |
Output is correct |
35 |
Correct |
81 ms |
43468 KB |
Output is correct |
36 |
Correct |
9 ms |
28012 KB |
Output is correct |
37 |
Correct |
7 ms |
27996 KB |
Output is correct |
38 |
Correct |
2293 ms |
261664 KB |
Output is correct |
39 |
Correct |
98 ms |
43472 KB |
Output is correct |
40 |
Correct |
73 ms |
42992 KB |
Output is correct |
41 |
Correct |
76 ms |
42844 KB |
Output is correct |
42 |
Correct |
94 ms |
43352 KB |
Output is correct |
43 |
Correct |
94 ms |
43284 KB |
Output is correct |
44 |
Correct |
409 ms |
51644 KB |
Output is correct |
45 |
Correct |
84 ms |
43468 KB |
Output is correct |
46 |
Correct |
84 ms |
43484 KB |
Output is correct |
47 |
Correct |
95 ms |
43312 KB |
Output is correct |
48 |
Correct |
412 ms |
51916 KB |
Output is correct |
49 |
Correct |
69 ms |
42588 KB |
Output is correct |
50 |
Correct |
82 ms |
43160 KB |
Output is correct |
51 |
Correct |
78 ms |
42844 KB |
Output is correct |
52 |
Correct |
92 ms |
42844 KB |
Output is correct |
53 |
Correct |
1971 ms |
250580 KB |
Output is correct |
54 |
Correct |
1906 ms |
250576 KB |
Output is correct |
55 |
Correct |
2235 ms |
259900 KB |
Output is correct |
56 |
Correct |
2235 ms |
259908 KB |
Output is correct |
57 |
Correct |
2188 ms |
261672 KB |
Output is correct |
58 |
Correct |
2199 ms |
261668 KB |
Output is correct |
59 |
Correct |
2246 ms |
261668 KB |
Output is correct |
60 |
Correct |
2383 ms |
257540 KB |
Output is correct |
61 |
Correct |
1667 ms |
239376 KB |
Output is correct |
62 |
Correct |
2224 ms |
253656 KB |
Output is correct |
63 |
Correct |
2020 ms |
249376 KB |
Output is correct |
64 |
Correct |
1897 ms |
244648 KB |
Output is correct |