#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], prfx[n + 1][26], sufx[n + 1][26];
for (int j = 0; j < 26; j++) prfx[n][j] = sufx[n][j] = dp[n][j] = 1;
for (int j = 1; j < 26; j++) prfx[n][j] += prfx[n][j - 1];
for (int j = 24; j >= 0; j--) sufx[n][j] += sufx[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);
if (j - 1 >= 0) sum[j][0] += prfx[i + 1][j - 1];
active[j][1].insert(i);
if (j + 1 < 26) sum[j][1] += sufx[i + 1][j + 1];
for (auto en : st[i][0]) {
auto it = active[j][1].lower_bound(i);
while (it != active[j][1].end() && *it < en) {
if (j + 1 < 26) sum[j][1] -= sufx[*it + 1][j + 1];
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) {
if (j - 1 >= 0) sum[j][0] -= prfx[*it + 1][j - 1];
active[j][0].erase(it);
it = active[j][0].lower_bound(i);
}
}
prfx[i][j] = sufx[i][j] = dp[i][j] = sum[j][0] + sum[j][1] + 1;
}
for (int j = 1; j < 26; j++) {
prfx[i][j] += prfx[i][j - 1];
}
for (int j = 24; j >= 0; j--) {
sufx[i][j] += sufx[i][j + 1];
}
}
mint ans = 0;
for (int j = 0; j < 26; j++) {
ans += dp[1][j];
}
cout << ans << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 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 |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
344 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 |
1 ms |
444 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 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 |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
344 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 |
1 ms |
444 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
600 KB |
Output is correct |
16 |
Correct |
1 ms |
604 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
2 ms |
344 KB |
Output is correct |
21 |
Correct |
1 ms |
344 KB |
Output is correct |
22 |
Correct |
3 ms |
600 KB |
Output is correct |
23 |
Correct |
1 ms |
860 KB |
Output is correct |
24 |
Correct |
1 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1372 ms |
198952 KB |
Output is correct |
6 |
Correct |
1366 ms |
199004 KB |
Output is correct |
7 |
Correct |
1385 ms |
198996 KB |
Output is correct |
8 |
Correct |
1325 ms |
198996 KB |
Output is correct |
9 |
Correct |
1373 ms |
198996 KB |
Output is correct |
10 |
Correct |
62 ms |
8284 KB |
Output is correct |
11 |
Correct |
2 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1741 ms |
202672 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 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 |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
344 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 |
1 ms |
444 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
600 KB |
Output is correct |
16 |
Correct |
1 ms |
604 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
2 ms |
344 KB |
Output is correct |
21 |
Correct |
1 ms |
344 KB |
Output is correct |
22 |
Correct |
3 ms |
600 KB |
Output is correct |
23 |
Correct |
1 ms |
860 KB |
Output is correct |
24 |
Correct |
1 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
51 ms |
8280 KB |
Output is correct |
27 |
Correct |
139 ms |
32084 KB |
Output is correct |
28 |
Correct |
142 ms |
32200 KB |
Output is correct |
29 |
Correct |
80 ms |
10688 KB |
Output is correct |
30 |
Correct |
69 ms |
10588 KB |
Output is correct |
31 |
Correct |
192 ms |
18516 KB |
Output is correct |
32 |
Correct |
59 ms |
8360 KB |
Output is correct |
33 |
Correct |
69 ms |
8284 KB |
Output is correct |
34 |
Correct |
68 ms |
8540 KB |
Output is correct |
35 |
Correct |
145 ms |
16744 KB |
Output is correct |
36 |
Correct |
259 ms |
54220 KB |
Output is correct |
37 |
Correct |
67 ms |
8540 KB |
Output is correct |
38 |
Correct |
70 ms |
8280 KB |
Output is correct |
39 |
Correct |
83 ms |
9052 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 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 |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
344 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 |
1 ms |
444 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
600 KB |
Output is correct |
16 |
Correct |
1 ms |
604 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
2 ms |
344 KB |
Output is correct |
21 |
Correct |
1 ms |
344 KB |
Output is correct |
22 |
Correct |
3 ms |
600 KB |
Output is correct |
23 |
Correct |
1 ms |
860 KB |
Output is correct |
24 |
Correct |
1 ms |
604 KB |
Output is correct |
25 |
Correct |
1 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 |
0 ms |
348 KB |
Output is correct |
30 |
Correct |
1372 ms |
198952 KB |
Output is correct |
31 |
Correct |
1366 ms |
199004 KB |
Output is correct |
32 |
Correct |
1385 ms |
198996 KB |
Output is correct |
33 |
Correct |
1325 ms |
198996 KB |
Output is correct |
34 |
Correct |
1373 ms |
198996 KB |
Output is correct |
35 |
Correct |
62 ms |
8284 KB |
Output is correct |
36 |
Correct |
2 ms |
344 KB |
Output is correct |
37 |
Correct |
1 ms |
348 KB |
Output is correct |
38 |
Correct |
1741 ms |
202672 KB |
Output is correct |
39 |
Correct |
51 ms |
8280 KB |
Output is correct |
40 |
Correct |
139 ms |
32084 KB |
Output is correct |
41 |
Correct |
142 ms |
32200 KB |
Output is correct |
42 |
Correct |
80 ms |
10688 KB |
Output is correct |
43 |
Correct |
69 ms |
10588 KB |
Output is correct |
44 |
Correct |
192 ms |
18516 KB |
Output is correct |
45 |
Correct |
59 ms |
8360 KB |
Output is correct |
46 |
Correct |
69 ms |
8284 KB |
Output is correct |
47 |
Correct |
68 ms |
8540 KB |
Output is correct |
48 |
Correct |
145 ms |
16744 KB |
Output is correct |
49 |
Correct |
259 ms |
54220 KB |
Output is correct |
50 |
Correct |
67 ms |
8540 KB |
Output is correct |
51 |
Correct |
70 ms |
8280 KB |
Output is correct |
52 |
Correct |
83 ms |
9052 KB |
Output is correct |
53 |
Execution timed out |
4021 ms |
249372 KB |
Time limit exceeded |
54 |
Halted |
0 ms |
0 KB |
- |