#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#ifndef LOCAL
// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#endif
using namespace std;
using ll = long long;
using ld = long double;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
mt19937_64 mt(time(0));
void solve();
void init();
int32_t main() {
#ifndef LOCAL
cin.tie(nullptr)->sync_with_stdio(false);
#endif
cout << fixed << setprecision(30);
init();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
const int LG = 19, N = 1 << LG, A = 26, mod = 1000000007;
int to_up[N], to_down[N], dp[N][A];
int add(int a, int b) {
return a + b >= mod ? a + b - mod : a + b;
}
int sub(int a, int b) {
return a >= b ? a - b : a - b + mod;
}
int mul(int a, int b) {
return 1ll * a * b % mod;
}
int bin_pow(int a, int x) {
int res = 1;
while (x) {
if (x & 1) {
res = mul(res, a);
}
a = mul(a, a);
x >>= 1;
}
return res;
}
struct segment_tree {
vector<int> st;
int size;
segment_tree(int sz = N) {
size = sz;
st.resize(2 * size, -1);
}
void update(int l, int r, int v) {
l += size;
r += size;
while (l <= r) {
if (l & 1) {
st[l] = max(st[l], v);
l++;
}
if (~r & 1) {
st[r] = max(st[r], v);
r--;
}
l >>= 1;
r >>= 1;
}
}
int get(int i) {
i += size;
int res = -1;
while (i) {
res = max(st[i], res);
i >>= 1;
}
return res;
}
};
void init() {}
void solve() {
int n, m;
cin >> n >> m;
segment_tree stl, str;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b; a--; b--;
if (a < b) {
str.update(a + 1, b, a);
} else {
stl.update(b + 1, a, b);
}
}
for (int i = 0; i < n; i++) {
to_up[i] = stl.get(i);
to_down[i] = str.get(i);
}
for (int i = 0; i < A; i++) {
dp[0][i] = 1;
}
// for (int i = 0; i < n; i++) {
// cout << to_up[i] << ' ';
// }
// cout << '\n';
// for (int i = 0; i < n; i++) {
// cout << to_down[i] << ' ';
// }
// cout << '\n';
for (int i = 1; i < n; i++) {
for (int j = 0; j < A; j++) {
int up = 0, down = 0, plate = 0, anywhere = 0;
if (to_up[i] != -1) {
up = dp[to_up[i]][j];
}
if (to_down[i] != -1) {
down = dp[to_down[i]][j];
}
if (to_up[i] > to_down[i]) {
plate = down;
} else {
plate = up;
}
anywhere = sub(dp[i - 1][j], sub(add(up, down), plate));
// cout << i << ' ' << j << ' ' << plate << ' ' << up << ' ' << down << ' ' << anywhere << '\n';
up = sub(up, plate);
down = sub(down, plate);
for (int l = 0; l < A; l++) {
dp[i][l] = add(dp[i][l], anywhere);
if (l <= j) {
dp[i][l] = add(dp[i][l], down);
}
if (l >= j) {
dp[i][l] = add(dp[i][l], up);
}
if (l == j) {
dp[i][l] = add(dp[i][l], plate);
}
}
}
}
int ans = 0;
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < A; j++) {
// cout << dp[i][j] << ' ';
// }
// cout << '\n';
// }
for (int i = 0; i < A; i++) {
ans = add(ans, dp[n - 1][i]);
}
cout << ans << '\n';
// cout << sub(bin_pow(A, n), ans) << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
12636 KB |
Output is correct |
2 |
Correct |
3 ms |
12636 KB |
Output is correct |
3 |
Correct |
3 ms |
12632 KB |
Output is correct |
4 |
Correct |
5 ms |
12636 KB |
Output is correct |
5 |
Correct |
3 ms |
12636 KB |
Output is correct |
6 |
Correct |
3 ms |
12636 KB |
Output is correct |
7 |
Correct |
4 ms |
12636 KB |
Output is correct |
8 |
Correct |
4 ms |
12636 KB |
Output is correct |
9 |
Correct |
3 ms |
12636 KB |
Output is correct |
10 |
Correct |
3 ms |
12636 KB |
Output is correct |
11 |
Correct |
3 ms |
12752 KB |
Output is correct |
12 |
Correct |
3 ms |
12636 KB |
Output is correct |
13 |
Correct |
3 ms |
12636 KB |
Output is correct |
14 |
Correct |
4 ms |
12636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
12636 KB |
Output is correct |
2 |
Correct |
3 ms |
12636 KB |
Output is correct |
3 |
Correct |
3 ms |
12632 KB |
Output is correct |
4 |
Correct |
5 ms |
12636 KB |
Output is correct |
5 |
Correct |
3 ms |
12636 KB |
Output is correct |
6 |
Correct |
3 ms |
12636 KB |
Output is correct |
7 |
Correct |
4 ms |
12636 KB |
Output is correct |
8 |
Correct |
4 ms |
12636 KB |
Output is correct |
9 |
Correct |
3 ms |
12636 KB |
Output is correct |
10 |
Correct |
3 ms |
12636 KB |
Output is correct |
11 |
Correct |
3 ms |
12752 KB |
Output is correct |
12 |
Correct |
3 ms |
12636 KB |
Output is correct |
13 |
Correct |
3 ms |
12636 KB |
Output is correct |
14 |
Correct |
4 ms |
12636 KB |
Output is correct |
15 |
Correct |
4 ms |
12636 KB |
Output is correct |
16 |
Correct |
4 ms |
12636 KB |
Output is correct |
17 |
Correct |
3 ms |
12636 KB |
Output is correct |
18 |
Correct |
4 ms |
12636 KB |
Output is correct |
19 |
Correct |
4 ms |
12636 KB |
Output is correct |
20 |
Correct |
4 ms |
12636 KB |
Output is correct |
21 |
Correct |
3 ms |
12636 KB |
Output is correct |
22 |
Correct |
5 ms |
12892 KB |
Output is correct |
23 |
Correct |
4 ms |
12636 KB |
Output is correct |
24 |
Correct |
4 ms |
12704 KB |
Output is correct |
25 |
Correct |
4 ms |
12632 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
12636 KB |
Output is correct |
2 |
Correct |
3 ms |
12632 KB |
Output is correct |
3 |
Correct |
3 ms |
12636 KB |
Output is correct |
4 |
Correct |
3 ms |
12636 KB |
Output is correct |
5 |
Correct |
668 ms |
71824 KB |
Output is correct |
6 |
Correct |
678 ms |
72136 KB |
Output is correct |
7 |
Correct |
698 ms |
72040 KB |
Output is correct |
8 |
Correct |
696 ms |
71956 KB |
Output is correct |
9 |
Correct |
682 ms |
71868 KB |
Output is correct |
10 |
Correct |
30 ms |
14932 KB |
Output is correct |
11 |
Correct |
3 ms |
12636 KB |
Output is correct |
12 |
Correct |
4 ms |
12760 KB |
Output is correct |
13 |
Correct |
739 ms |
72308 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
12636 KB |
Output is correct |
2 |
Correct |
3 ms |
12636 KB |
Output is correct |
3 |
Correct |
3 ms |
12632 KB |
Output is correct |
4 |
Correct |
5 ms |
12636 KB |
Output is correct |
5 |
Correct |
3 ms |
12636 KB |
Output is correct |
6 |
Correct |
3 ms |
12636 KB |
Output is correct |
7 |
Correct |
4 ms |
12636 KB |
Output is correct |
8 |
Correct |
4 ms |
12636 KB |
Output is correct |
9 |
Correct |
3 ms |
12636 KB |
Output is correct |
10 |
Correct |
3 ms |
12636 KB |
Output is correct |
11 |
Correct |
3 ms |
12752 KB |
Output is correct |
12 |
Correct |
3 ms |
12636 KB |
Output is correct |
13 |
Correct |
3 ms |
12636 KB |
Output is correct |
14 |
Correct |
4 ms |
12636 KB |
Output is correct |
15 |
Correct |
4 ms |
12636 KB |
Output is correct |
16 |
Correct |
4 ms |
12636 KB |
Output is correct |
17 |
Correct |
3 ms |
12636 KB |
Output is correct |
18 |
Correct |
4 ms |
12636 KB |
Output is correct |
19 |
Correct |
4 ms |
12636 KB |
Output is correct |
20 |
Correct |
4 ms |
12636 KB |
Output is correct |
21 |
Correct |
3 ms |
12636 KB |
Output is correct |
22 |
Correct |
5 ms |
12892 KB |
Output is correct |
23 |
Correct |
4 ms |
12636 KB |
Output is correct |
24 |
Correct |
4 ms |
12704 KB |
Output is correct |
25 |
Correct |
4 ms |
12632 KB |
Output is correct |
26 |
Correct |
30 ms |
14928 KB |
Output is correct |
27 |
Correct |
40 ms |
14676 KB |
Output is correct |
28 |
Correct |
31 ms |
14696 KB |
Output is correct |
29 |
Correct |
34 ms |
14940 KB |
Output is correct |
30 |
Correct |
31 ms |
14932 KB |
Output is correct |
31 |
Correct |
124 ms |
20048 KB |
Output is correct |
32 |
Correct |
30 ms |
14928 KB |
Output is correct |
33 |
Correct |
30 ms |
14804 KB |
Output is correct |
34 |
Correct |
32 ms |
14788 KB |
Output is correct |
35 |
Correct |
136 ms |
20048 KB |
Output is correct |
36 |
Correct |
31 ms |
14672 KB |
Output is correct |
37 |
Correct |
31 ms |
14928 KB |
Output is correct |
38 |
Correct |
30 ms |
14940 KB |
Output is correct |
39 |
Correct |
28 ms |
14740 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
12636 KB |
Output is correct |
2 |
Correct |
3 ms |
12636 KB |
Output is correct |
3 |
Correct |
3 ms |
12632 KB |
Output is correct |
4 |
Correct |
5 ms |
12636 KB |
Output is correct |
5 |
Correct |
3 ms |
12636 KB |
Output is correct |
6 |
Correct |
3 ms |
12636 KB |
Output is correct |
7 |
Correct |
4 ms |
12636 KB |
Output is correct |
8 |
Correct |
4 ms |
12636 KB |
Output is correct |
9 |
Correct |
3 ms |
12636 KB |
Output is correct |
10 |
Correct |
3 ms |
12636 KB |
Output is correct |
11 |
Correct |
3 ms |
12752 KB |
Output is correct |
12 |
Correct |
3 ms |
12636 KB |
Output is correct |
13 |
Correct |
3 ms |
12636 KB |
Output is correct |
14 |
Correct |
4 ms |
12636 KB |
Output is correct |
15 |
Correct |
4 ms |
12636 KB |
Output is correct |
16 |
Correct |
4 ms |
12636 KB |
Output is correct |
17 |
Correct |
3 ms |
12636 KB |
Output is correct |
18 |
Correct |
4 ms |
12636 KB |
Output is correct |
19 |
Correct |
4 ms |
12636 KB |
Output is correct |
20 |
Correct |
4 ms |
12636 KB |
Output is correct |
21 |
Correct |
3 ms |
12636 KB |
Output is correct |
22 |
Correct |
5 ms |
12892 KB |
Output is correct |
23 |
Correct |
4 ms |
12636 KB |
Output is correct |
24 |
Correct |
4 ms |
12704 KB |
Output is correct |
25 |
Correct |
4 ms |
12632 KB |
Output is correct |
26 |
Correct |
4 ms |
12636 KB |
Output is correct |
27 |
Correct |
3 ms |
12632 KB |
Output is correct |
28 |
Correct |
3 ms |
12636 KB |
Output is correct |
29 |
Correct |
3 ms |
12636 KB |
Output is correct |
30 |
Correct |
668 ms |
71824 KB |
Output is correct |
31 |
Correct |
678 ms |
72136 KB |
Output is correct |
32 |
Correct |
698 ms |
72040 KB |
Output is correct |
33 |
Correct |
696 ms |
71956 KB |
Output is correct |
34 |
Correct |
682 ms |
71868 KB |
Output is correct |
35 |
Correct |
30 ms |
14932 KB |
Output is correct |
36 |
Correct |
3 ms |
12636 KB |
Output is correct |
37 |
Correct |
4 ms |
12760 KB |
Output is correct |
38 |
Correct |
739 ms |
72308 KB |
Output is correct |
39 |
Correct |
30 ms |
14928 KB |
Output is correct |
40 |
Correct |
40 ms |
14676 KB |
Output is correct |
41 |
Correct |
31 ms |
14696 KB |
Output is correct |
42 |
Correct |
34 ms |
14940 KB |
Output is correct |
43 |
Correct |
31 ms |
14932 KB |
Output is correct |
44 |
Correct |
124 ms |
20048 KB |
Output is correct |
45 |
Correct |
30 ms |
14928 KB |
Output is correct |
46 |
Correct |
30 ms |
14804 KB |
Output is correct |
47 |
Correct |
32 ms |
14788 KB |
Output is correct |
48 |
Correct |
136 ms |
20048 KB |
Output is correct |
49 |
Correct |
31 ms |
14672 KB |
Output is correct |
50 |
Correct |
31 ms |
14928 KB |
Output is correct |
51 |
Correct |
30 ms |
14940 KB |
Output is correct |
52 |
Correct |
28 ms |
14740 KB |
Output is correct |
53 |
Correct |
671 ms |
68688 KB |
Output is correct |
54 |
Correct |
726 ms |
68656 KB |
Output is correct |
55 |
Correct |
732 ms |
72360 KB |
Output is correct |
56 |
Correct |
744 ms |
72012 KB |
Output is correct |
57 |
Correct |
696 ms |
72032 KB |
Output is correct |
58 |
Correct |
666 ms |
71904 KB |
Output is correct |
59 |
Correct |
716 ms |
71884 KB |
Output is correct |
60 |
Correct |
783 ms |
71920 KB |
Output is correct |
61 |
Correct |
651 ms |
65452 KB |
Output is correct |
62 |
Correct |
764 ms |
70364 KB |
Output is correct |
63 |
Correct |
737 ms |
68724 KB |
Output is correct |
64 |
Correct |
676 ms |
67108 KB |
Output is correct |