#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;
struct mint {
int v;
mint(long long x) {
if (x >= mod) x %= mod;
v = x;
}
mint() {v = 0;}
mint& operator+=(mint b) {
if ((v += b.v) >= mod) {
v -= mod;
}
return *this;
}
mint& operator-=(mint b) {
if ((v -= b.v) < 0) {
v += mod;
}
return *this;
}
mint& operator*=(mint b) {
v = 1ll * v * b.v % mod;
return *this;
}
mint power(mint a, int b) {
mint ans = 1;
while (b) {
if (b & 1) {
ans *= a;
}
a *= a, b >>= 1;
}
return ans;
}
mint& operator/=(mint b) {
v = 1ll * v * power(b, mod - 2).v % mod;
return *this;
}
friend mint operator+(mint a, mint b) {
return a += b;
}
friend mint operator-(mint a, mint b) {
return a -= b;
}
friend mint operator*(mint a, mint b) {
return a *= b;
}
friend mint operator/(mint a, mint b) {
return a /= b;
}
friend istream& operator>>(istream &is, mint a) {
return is >> a.v;
}
friend ostream& operator<<(ostream &os, mint a) {
return os << a.v;
}
};
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> st[n][2];
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
a--, b--;
if (a < b) {
//s[i - 1] > s[i]
st[a + 1][0].push_back(b + 1);
} else {
//s[i - 1] < s[i]
st[b + 1][1].push_back(a + 1);
}
}
mint dp[n + 1][26];
for (int j = 0; j < 26; j++) dp[n][j] = 1;
set<int> active[26][2];
mint sum[26][2];
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < 26; j++) {
active[j][0].insert(i);
for (int l = 0; l < j; l++) {
sum[j][0] += dp[i + 1][l];
}
active[j][1].insert(i);
for (int l = j + 1; l < 26; l++) {
sum[j][1] += dp[i + 1][l];
}
for (auto en : st[i][0]) {
auto it = active[j][1].lower_bound(i);
while (it != active[j][1].end() && *it < en) {
for (int l = j + 1; l < 26; l++) {
sum[j][1] -= dp[*it + 1][l];
}
active[j][1].erase(it);
it = active[j][1].lower_bound(i);
}
}
for (auto en : st[i][1]) {
auto it = active[j][0].lower_bound(i);
while (it != active[j][0].end() && *it < en) {
for (int l = 0; l < j; l++) {
sum[j][0] -= dp[*it + 1][l];
}
active[j][0].erase(it);
it = active[j][0].lower_bound(i);
}
}
dp[i][j] = sum[j][0] + sum[j][1] + 1;
}
}
mint ans = 0;
for (int j = 0; j < 26; j++) {
ans += dp[1][j];
}
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
600 KB |
Output is correct |
16 |
Correct |
2 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
2 ms |
344 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
3 ms |
600 KB |
Output is correct |
23 |
Correct |
2 ms |
856 KB |
Output is correct |
24 |
Correct |
2 ms |
600 KB |
Output is correct |
25 |
Correct |
2 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1894 ms |
97104 KB |
Output is correct |
6 |
Correct |
1888 ms |
97092 KB |
Output is correct |
7 |
Correct |
1936 ms |
97108 KB |
Output is correct |
8 |
Correct |
1864 ms |
97108 KB |
Output is correct |
9 |
Correct |
1916 ms |
97104 KB |
Output is correct |
10 |
Correct |
72 ms |
4188 KB |
Output is correct |
11 |
Correct |
2 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
2406 ms |
100700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
600 KB |
Output is correct |
16 |
Correct |
2 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
2 ms |
344 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
3 ms |
600 KB |
Output is correct |
23 |
Correct |
2 ms |
856 KB |
Output is correct |
24 |
Correct |
2 ms |
600 KB |
Output is correct |
25 |
Correct |
2 ms |
348 KB |
Output is correct |
26 |
Correct |
74 ms |
4188 KB |
Output is correct |
27 |
Correct |
169 ms |
28252 KB |
Output is correct |
28 |
Correct |
170 ms |
28128 KB |
Output is correct |
29 |
Correct |
98 ms |
6624 KB |
Output is correct |
30 |
Correct |
101 ms |
6616 KB |
Output is correct |
31 |
Correct |
221 ms |
14348 KB |
Output is correct |
32 |
Correct |
80 ms |
4188 KB |
Output is correct |
33 |
Correct |
77 ms |
4272 KB |
Output is correct |
34 |
Correct |
102 ms |
4556 KB |
Output is correct |
35 |
Correct |
171 ms |
12648 KB |
Output is correct |
36 |
Correct |
264 ms |
50004 KB |
Output is correct |
37 |
Correct |
104 ms |
4444 KB |
Output is correct |
38 |
Correct |
114 ms |
4312 KB |
Output is correct |
39 |
Correct |
121 ms |
5048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
600 KB |
Output is correct |
16 |
Correct |
2 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
2 ms |
344 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
3 ms |
600 KB |
Output is correct |
23 |
Correct |
2 ms |
856 KB |
Output is correct |
24 |
Correct |
2 ms |
600 KB |
Output is correct |
25 |
Correct |
2 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
348 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
348 KB |
Output is correct |
30 |
Correct |
1894 ms |
97104 KB |
Output is correct |
31 |
Correct |
1888 ms |
97092 KB |
Output is correct |
32 |
Correct |
1936 ms |
97108 KB |
Output is correct |
33 |
Correct |
1864 ms |
97108 KB |
Output is correct |
34 |
Correct |
1916 ms |
97104 KB |
Output is correct |
35 |
Correct |
72 ms |
4188 KB |
Output is correct |
36 |
Correct |
2 ms |
344 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
38 |
Correct |
2406 ms |
100700 KB |
Output is correct |
39 |
Correct |
74 ms |
4188 KB |
Output is correct |
40 |
Correct |
169 ms |
28252 KB |
Output is correct |
41 |
Correct |
170 ms |
28128 KB |
Output is correct |
42 |
Correct |
98 ms |
6624 KB |
Output is correct |
43 |
Correct |
101 ms |
6616 KB |
Output is correct |
44 |
Correct |
221 ms |
14348 KB |
Output is correct |
45 |
Correct |
80 ms |
4188 KB |
Output is correct |
46 |
Correct |
77 ms |
4272 KB |
Output is correct |
47 |
Correct |
102 ms |
4556 KB |
Output is correct |
48 |
Correct |
171 ms |
12648 KB |
Output is correct |
49 |
Correct |
264 ms |
50004 KB |
Output is correct |
50 |
Correct |
104 ms |
4444 KB |
Output is correct |
51 |
Correct |
114 ms |
4312 KB |
Output is correct |
52 |
Correct |
121 ms |
5048 KB |
Output is correct |
53 |
Execution timed out |
4064 ms |
147540 KB |
Time limit exceeded |
54 |
Halted |
0 ms |
0 KB |
- |