#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <queue>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#define DEBUG
const int INF = (int)1e9 + 7;
using namespace std;
vector<int> A[505050];
vector<int> B[505050];
priority_queue<pii> C, D;
long long dp[505050][26];
long long L[505050][26];
long long R[505050][26];
long long S[505050];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m; cin >> n >> m;
for(int i = 0; i < m; ++i)
{
int x, y; cin >> x >> y;
if(x > y) A[y].push_back(x);
else B[x].push_back(y);
}
for(int i = 0; i < 26; ++i) dp[1][i] = 1, L[1][i] = i, R[1][i] = 25 - i, S[1] = 26;
for(int i = 1; i < n; ++i)
{
for(auto j : A[i]) C.push({i, j});
for(auto j : B[i]) D.push({i, j});
while(C.size() && C.top().ss <= i) C.pop();
while(D.size() && D.top().ss <= i) D.pop();
int x = (C.size() ? C.top().ff : 0);
int y = (D.size() ? D.top().ff : 0);
int z = max(x, y);
for(int j = 0; j < 26; ++j) dp[i + 1][j] = (2 * INF + dp[i][j] + (S[i] - S[z]) - (dp[i][j] - dp[z][j])) % INF;
if(x > y) for(int j = 0; j < 26; ++j) dp[i + 1][j] = (INF + dp[i + 1][j] + (L[x][j] - L[y][j])) % INF;
if(x < y) for(int j = 0; j < 26; ++j) dp[i + 1][j] = (INF + dp[i + 1][j] + (R[y][j] - R[x][j])) % INF;
for(int j = 1; j < 26; ++j) L[i + 1][j] = (L[i + 1][j - 1] + dp[i + 1][j - 1]) % INF;
for(int j = 24; j >= 0; --j) R[i + 1][j] = (R[i + 1][j + 1] + dp[i + 1][j + 1]) % INF;
for(int j = 0; j < 26; ++j) S[i + 1] = (S[i + 1] + dp[i + 1][j]) % INF;
}
cout << S[n];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
24020 KB |
Output is correct |
2 |
Correct |
12 ms |
24048 KB |
Output is correct |
3 |
Correct |
12 ms |
23968 KB |
Output is correct |
4 |
Correct |
13 ms |
24036 KB |
Output is correct |
5 |
Correct |
12 ms |
24048 KB |
Output is correct |
6 |
Correct |
13 ms |
24060 KB |
Output is correct |
7 |
Correct |
12 ms |
24020 KB |
Output is correct |
8 |
Correct |
13 ms |
24020 KB |
Output is correct |
9 |
Correct |
12 ms |
24012 KB |
Output is correct |
10 |
Correct |
12 ms |
24020 KB |
Output is correct |
11 |
Correct |
13 ms |
23968 KB |
Output is correct |
12 |
Correct |
12 ms |
24060 KB |
Output is correct |
13 |
Correct |
13 ms |
24020 KB |
Output is correct |
14 |
Correct |
12 ms |
24044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
24020 KB |
Output is correct |
2 |
Correct |
12 ms |
24048 KB |
Output is correct |
3 |
Correct |
12 ms |
23968 KB |
Output is correct |
4 |
Correct |
13 ms |
24036 KB |
Output is correct |
5 |
Correct |
12 ms |
24048 KB |
Output is correct |
6 |
Correct |
13 ms |
24060 KB |
Output is correct |
7 |
Correct |
12 ms |
24020 KB |
Output is correct |
8 |
Correct |
13 ms |
24020 KB |
Output is correct |
9 |
Correct |
12 ms |
24012 KB |
Output is correct |
10 |
Correct |
12 ms |
24020 KB |
Output is correct |
11 |
Correct |
13 ms |
23968 KB |
Output is correct |
12 |
Correct |
12 ms |
24060 KB |
Output is correct |
13 |
Correct |
13 ms |
24020 KB |
Output is correct |
14 |
Correct |
12 ms |
24044 KB |
Output is correct |
15 |
Correct |
13 ms |
24200 KB |
Output is correct |
16 |
Correct |
14 ms |
24120 KB |
Output is correct |
17 |
Correct |
13 ms |
24176 KB |
Output is correct |
18 |
Correct |
12 ms |
24148 KB |
Output is correct |
19 |
Correct |
14 ms |
24176 KB |
Output is correct |
20 |
Correct |
12 ms |
24172 KB |
Output is correct |
21 |
Correct |
15 ms |
24216 KB |
Output is correct |
22 |
Correct |
15 ms |
24532 KB |
Output is correct |
23 |
Correct |
12 ms |
24172 KB |
Output is correct |
24 |
Correct |
11 ms |
24148 KB |
Output is correct |
25 |
Correct |
12 ms |
24148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
24040 KB |
Output is correct |
2 |
Correct |
12 ms |
24128 KB |
Output is correct |
3 |
Correct |
12 ms |
24048 KB |
Output is correct |
4 |
Correct |
13 ms |
24144 KB |
Output is correct |
5 |
Correct |
522 ms |
358936 KB |
Output is correct |
6 |
Correct |
502 ms |
358948 KB |
Output is correct |
7 |
Correct |
494 ms |
358868 KB |
Output is correct |
8 |
Correct |
504 ms |
359252 KB |
Output is correct |
9 |
Correct |
497 ms |
358656 KB |
Output is correct |
10 |
Correct |
31 ms |
37460 KB |
Output is correct |
11 |
Correct |
13 ms |
24172 KB |
Output is correct |
12 |
Correct |
12 ms |
24044 KB |
Output is correct |
13 |
Correct |
633 ms |
359496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
24020 KB |
Output is correct |
2 |
Correct |
12 ms |
24048 KB |
Output is correct |
3 |
Correct |
12 ms |
23968 KB |
Output is correct |
4 |
Correct |
13 ms |
24036 KB |
Output is correct |
5 |
Correct |
12 ms |
24048 KB |
Output is correct |
6 |
Correct |
13 ms |
24060 KB |
Output is correct |
7 |
Correct |
12 ms |
24020 KB |
Output is correct |
8 |
Correct |
13 ms |
24020 KB |
Output is correct |
9 |
Correct |
12 ms |
24012 KB |
Output is correct |
10 |
Correct |
12 ms |
24020 KB |
Output is correct |
11 |
Correct |
13 ms |
23968 KB |
Output is correct |
12 |
Correct |
12 ms |
24060 KB |
Output is correct |
13 |
Correct |
13 ms |
24020 KB |
Output is correct |
14 |
Correct |
12 ms |
24044 KB |
Output is correct |
15 |
Correct |
13 ms |
24200 KB |
Output is correct |
16 |
Correct |
14 ms |
24120 KB |
Output is correct |
17 |
Correct |
13 ms |
24176 KB |
Output is correct |
18 |
Correct |
12 ms |
24148 KB |
Output is correct |
19 |
Correct |
14 ms |
24176 KB |
Output is correct |
20 |
Correct |
12 ms |
24172 KB |
Output is correct |
21 |
Correct |
15 ms |
24216 KB |
Output is correct |
22 |
Correct |
15 ms |
24532 KB |
Output is correct |
23 |
Correct |
12 ms |
24172 KB |
Output is correct |
24 |
Correct |
11 ms |
24148 KB |
Output is correct |
25 |
Correct |
12 ms |
24148 KB |
Output is correct |
26 |
Correct |
30 ms |
37460 KB |
Output is correct |
27 |
Correct |
28 ms |
36968 KB |
Output is correct |
28 |
Correct |
29 ms |
36964 KB |
Output is correct |
29 |
Correct |
32 ms |
37484 KB |
Output is correct |
30 |
Correct |
33 ms |
37412 KB |
Output is correct |
31 |
Correct |
181 ms |
49424 KB |
Output is correct |
32 |
Correct |
33 ms |
37324 KB |
Output is correct |
33 |
Correct |
32 ms |
37356 KB |
Output is correct |
34 |
Correct |
33 ms |
37396 KB |
Output is correct |
35 |
Correct |
148 ms |
49736 KB |
Output is correct |
36 |
Correct |
24 ms |
36376 KB |
Output is correct |
37 |
Correct |
30 ms |
37056 KB |
Output is correct |
38 |
Correct |
31 ms |
36960 KB |
Output is correct |
39 |
Correct |
28 ms |
36608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
24020 KB |
Output is correct |
2 |
Correct |
12 ms |
24048 KB |
Output is correct |
3 |
Correct |
12 ms |
23968 KB |
Output is correct |
4 |
Correct |
13 ms |
24036 KB |
Output is correct |
5 |
Correct |
12 ms |
24048 KB |
Output is correct |
6 |
Correct |
13 ms |
24060 KB |
Output is correct |
7 |
Correct |
12 ms |
24020 KB |
Output is correct |
8 |
Correct |
13 ms |
24020 KB |
Output is correct |
9 |
Correct |
12 ms |
24012 KB |
Output is correct |
10 |
Correct |
12 ms |
24020 KB |
Output is correct |
11 |
Correct |
13 ms |
23968 KB |
Output is correct |
12 |
Correct |
12 ms |
24060 KB |
Output is correct |
13 |
Correct |
13 ms |
24020 KB |
Output is correct |
14 |
Correct |
12 ms |
24044 KB |
Output is correct |
15 |
Correct |
13 ms |
24200 KB |
Output is correct |
16 |
Correct |
14 ms |
24120 KB |
Output is correct |
17 |
Correct |
13 ms |
24176 KB |
Output is correct |
18 |
Correct |
12 ms |
24148 KB |
Output is correct |
19 |
Correct |
14 ms |
24176 KB |
Output is correct |
20 |
Correct |
12 ms |
24172 KB |
Output is correct |
21 |
Correct |
15 ms |
24216 KB |
Output is correct |
22 |
Correct |
15 ms |
24532 KB |
Output is correct |
23 |
Correct |
12 ms |
24172 KB |
Output is correct |
24 |
Correct |
11 ms |
24148 KB |
Output is correct |
25 |
Correct |
12 ms |
24148 KB |
Output is correct |
26 |
Correct |
12 ms |
24040 KB |
Output is correct |
27 |
Correct |
12 ms |
24128 KB |
Output is correct |
28 |
Correct |
12 ms |
24048 KB |
Output is correct |
29 |
Correct |
13 ms |
24144 KB |
Output is correct |
30 |
Correct |
522 ms |
358936 KB |
Output is correct |
31 |
Correct |
502 ms |
358948 KB |
Output is correct |
32 |
Correct |
494 ms |
358868 KB |
Output is correct |
33 |
Correct |
504 ms |
359252 KB |
Output is correct |
34 |
Correct |
497 ms |
358656 KB |
Output is correct |
35 |
Correct |
31 ms |
37460 KB |
Output is correct |
36 |
Correct |
13 ms |
24172 KB |
Output is correct |
37 |
Correct |
12 ms |
24044 KB |
Output is correct |
38 |
Correct |
633 ms |
359496 KB |
Output is correct |
39 |
Correct |
30 ms |
37460 KB |
Output is correct |
40 |
Correct |
28 ms |
36968 KB |
Output is correct |
41 |
Correct |
29 ms |
36964 KB |
Output is correct |
42 |
Correct |
32 ms |
37484 KB |
Output is correct |
43 |
Correct |
33 ms |
37412 KB |
Output is correct |
44 |
Correct |
181 ms |
49424 KB |
Output is correct |
45 |
Correct |
33 ms |
37324 KB |
Output is correct |
46 |
Correct |
32 ms |
37356 KB |
Output is correct |
47 |
Correct |
33 ms |
37396 KB |
Output is correct |
48 |
Correct |
148 ms |
49736 KB |
Output is correct |
49 |
Correct |
24 ms |
36376 KB |
Output is correct |
50 |
Correct |
30 ms |
37056 KB |
Output is correct |
51 |
Correct |
31 ms |
36960 KB |
Output is correct |
52 |
Correct |
28 ms |
36608 KB |
Output is correct |
53 |
Correct |
441 ms |
346404 KB |
Output is correct |
54 |
Correct |
428 ms |
346524 KB |
Output is correct |
55 |
Correct |
554 ms |
357780 KB |
Output is correct |
56 |
Correct |
554 ms |
357804 KB |
Output is correct |
57 |
Correct |
511 ms |
358680 KB |
Output is correct |
58 |
Correct |
501 ms |
357712 KB |
Output is correct |
59 |
Correct |
492 ms |
358876 KB |
Output is correct |
60 |
Correct |
601 ms |
355596 KB |
Output is correct |
61 |
Correct |
382 ms |
333156 KB |
Output is correct |
62 |
Correct |
554 ms |
350564 KB |
Output is correct |
63 |
Correct |
499 ms |
345244 KB |
Output is correct |
64 |
Correct |
427 ms |
339596 KB |
Output is correct |