#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 20010, mod = 1e9+7;
int edge[maxn][2];
int dp[maxn][26]; // dp[pos][cor(grp(pos))]
inline int sum(int a, int b) { a += b; if(a >= mod) a -= mod; return a; }
inline int sub(int a, int b) { a -= b; if(a < 0) a += mod; return a; }
inline void add(int& a, int b) { a += b; if(a >= mod) a -= mod; }
int main() {
int n, m; scanf("%d %d", &n, &m);
for(int i = 1; i <= m; i++) {
int a, b, t = 0;
scanf("%d %d", &a, &b);
if(a > b)
swap(a, b), t = 1;
// t: 0 => color[group(a)] <= color[min(b, group(a)+1)], 1 => color[group(a)] >= color[min(b, group(a)+1)]
edge[a][t] = max(edge[a][t], b);
}
for(int cor = 0; cor < 26; cor++)
dp[1][cor] = 1;
int ans = 0;
for(int i = 1; i <= n; i++) {
int itv[2]{};
itv[0] = edge[i][0], itv[1] = edge[i][1];
int pref[26]{}, suf[26]{};
pref[0] = dp[i][0], suf[25] = dp[i][25];
for(int cor = 1; cor < 26; cor++)
pref[cor] = sum(pref[cor-1], dp[i][cor]);
for(int cor = 24; cor >= 0; cor--)
suf[cor] = sum(suf[cor+1], dp[i][cor]);
int tot = suf[0]; // só pra ficar mais legível depois
// printf("%d == %d\n", i, tot);
for(int j = i; j < n; j++) {
for(int flag : {0, 1})
itv[flag] = max(itv[flag], edge[j][flag]);
// printf("%d %d | %d %d\n", i, j, itv[0], itv[1]);
if(itv[0] > j && itv[1] > j)
continue;
if(itv[0] > j) // cor[grp[i]] <= cor[grp[j]]
for(int cor = 1; cor < 26; cor++)
add(dp[j+1][cor], pref[cor-1]);
if(itv[1] > j) // cor[grp[i]] >= cor[grp[j]]
for(int cor = 24; cor >= 0; cor--)
add(dp[j+1][cor], suf[cor+1]);
if(itv[0] <= j && itv[1] <= j) // eles só não podem ser da mesma cor senao taria recontando
for(int cor = 0; cor < 26; cor++)
add(dp[j+1][cor], sub(tot, dp[i][cor]));
}
add(ans, tot);
}
printf("%d\n", ans);
}
Compilation message
misspelling.cpp: In function 'int main()':
misspelling.cpp:18:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | int n, m; scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
misspelling.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
21 | scanf("%d %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
308 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
304 KB |
Output is correct |
22 |
Correct |
3 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Runtime error |
3 ms |
736 KB |
Execution killed with signal 11 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
308 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
304 KB |
Output is correct |
22 |
Correct |
3 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
269 ms |
2592 KB |
Output is correct |
27 |
Correct |
1628 ms |
2568 KB |
Output is correct |
28 |
Correct |
1687 ms |
2524 KB |
Output is correct |
29 |
Correct |
272 ms |
2504 KB |
Output is correct |
30 |
Correct |
301 ms |
2732 KB |
Output is correct |
31 |
Correct |
378 ms |
6240 KB |
Output is correct |
32 |
Correct |
276 ms |
2712 KB |
Output is correct |
33 |
Correct |
313 ms |
2640 KB |
Output is correct |
34 |
Correct |
269 ms |
2660 KB |
Output is correct |
35 |
Correct |
363 ms |
4088 KB |
Output is correct |
36 |
Correct |
2921 ms |
2324 KB |
Output is correct |
37 |
Correct |
292 ms |
2508 KB |
Output is correct |
38 |
Correct |
269 ms |
2604 KB |
Output is correct |
39 |
Correct |
297 ms |
2528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
308 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
304 KB |
Output is correct |
22 |
Correct |
3 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
0 ms |
212 KB |
Output is correct |
27 |
Correct |
0 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
212 KB |
Output is correct |
30 |
Runtime error |
3 ms |
736 KB |
Execution killed with signal 11 |
31 |
Halted |
0 ms |
0 KB |
- |