#include <cstdio>
#include <set>
#include <algorithm>
#include <vector>
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 5e5 + 500;
const int ALP = 30;
const int MOD = 1e9 + 7;
inline int add(int A, int B){
if(A + B >= MOD)
return A + B - MOD;
return A + B;
}
inline int sub(int A, int B){
if(A - B < 0)
return A - B + MOD;
return A - B;
}
inline int mul(int A, int B){
return (ll)A * B % MOD;
}
int n, q, A[N], B[N], P[N][ALP], gran[N][2];
vector < int > ubac[N][2];
set < int > S[2];
int main(){
scanf("%d%d", &n, &q);
for(int i = 0;i < q;i++){
scanf("%d%d", A + i, B + i);
ubac[max(A[i], B[i])][A[i] < B[i]].PB(min(A[i], B[i]));
}
S[0].insert(0); S[1].insert(0);
for(int i = n;i >= 1;i--){
for(int k = 0;k < 2;k++){
for(int x : ubac[i][k]) S[k].insert(x);
while(*S[k].rbegin() == i)
S[k].erase(*S[k].rbegin());
}
gran[i][0] = *S[0].rbegin();
gran[i][1] = *S[1].rbegin();
}
for(int j = 0;j < 26;j++) P[1][j] = 1;
for(int i = 2;i <= n;i++){
int sve = max(gran[i][0], gran[i][1]);
//printf("%d %d\n", ubac[i][0], ubac[i][1]);
int uk = 0;
for(int j = 0;j < 26;j++)
uk = add(uk, sub(P[i - 1][j], P[sve][j]));
for(int j = 0;j < 26;j++)
P[i][j] = sub(uk, sub(P[i - 1][j], P[sve][j]));
if(gran[i][0] > gran[i][1]){ // >
uk = 0;
for(int j = 25;j >= 0;j--){
P[i][j] = add(P[i][j], uk);
uk = add(uk, sub(P[gran[i][0]][j], P[gran[i][1]][j]));
}
}
else if(gran[i][0] < gran[i][1]){ // <
uk = 0;
for(int j = 0;j < 26;j++){
P[i][j] = add(P[i][j], uk);
uk = add(uk, sub(P[gran[i][1]][j], P[gran[i][0]][j]));
}
}
for(int j = 0;j < 26;j++){
P[i][j] = add(P[i - 1][j], P[i][j]);
}
}
int uk = 0;
for(int j = 0;j < 26;j++)
uk = add(uk, P[n][j]);
printf("%d\n", uk);
return 0;
}
Compilation message
misspelling.cpp: In function 'int main()':
misspelling.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | scanf("%d%d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~
misspelling.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
39 | scanf("%d%d", A + i, B + i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
13 ms |
23804 KB |
Output is correct |
3 |
Correct |
12 ms |
23780 KB |
Output is correct |
4 |
Correct |
13 ms |
23752 KB |
Output is correct |
5 |
Correct |
12 ms |
23744 KB |
Output is correct |
6 |
Correct |
13 ms |
23764 KB |
Output is correct |
7 |
Correct |
13 ms |
23748 KB |
Output is correct |
8 |
Correct |
13 ms |
23796 KB |
Output is correct |
9 |
Correct |
14 ms |
23792 KB |
Output is correct |
10 |
Correct |
12 ms |
23764 KB |
Output is correct |
11 |
Correct |
14 ms |
23764 KB |
Output is correct |
12 |
Correct |
13 ms |
23832 KB |
Output is correct |
13 |
Correct |
13 ms |
23800 KB |
Output is correct |
14 |
Correct |
17 ms |
23712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
13 ms |
23804 KB |
Output is correct |
3 |
Correct |
12 ms |
23780 KB |
Output is correct |
4 |
Correct |
13 ms |
23752 KB |
Output is correct |
5 |
Correct |
12 ms |
23744 KB |
Output is correct |
6 |
Correct |
13 ms |
23764 KB |
Output is correct |
7 |
Correct |
13 ms |
23748 KB |
Output is correct |
8 |
Correct |
13 ms |
23796 KB |
Output is correct |
9 |
Correct |
14 ms |
23792 KB |
Output is correct |
10 |
Correct |
12 ms |
23764 KB |
Output is correct |
11 |
Correct |
14 ms |
23764 KB |
Output is correct |
12 |
Correct |
13 ms |
23832 KB |
Output is correct |
13 |
Correct |
13 ms |
23800 KB |
Output is correct |
14 |
Correct |
17 ms |
23712 KB |
Output is correct |
15 |
Correct |
16 ms |
23800 KB |
Output is correct |
16 |
Correct |
13 ms |
23764 KB |
Output is correct |
17 |
Correct |
16 ms |
23800 KB |
Output is correct |
18 |
Correct |
13 ms |
23764 KB |
Output is correct |
19 |
Correct |
13 ms |
23836 KB |
Output is correct |
20 |
Correct |
14 ms |
23756 KB |
Output is correct |
21 |
Correct |
13 ms |
23764 KB |
Output is correct |
22 |
Correct |
15 ms |
24048 KB |
Output is correct |
23 |
Correct |
12 ms |
23804 KB |
Output is correct |
24 |
Correct |
13 ms |
23764 KB |
Output is correct |
25 |
Correct |
14 ms |
23844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
23704 KB |
Output is correct |
2 |
Correct |
14 ms |
23764 KB |
Output is correct |
3 |
Correct |
15 ms |
23800 KB |
Output is correct |
4 |
Correct |
16 ms |
23732 KB |
Output is correct |
5 |
Correct |
282 ms |
112616 KB |
Output is correct |
6 |
Correct |
309 ms |
112612 KB |
Output is correct |
7 |
Correct |
330 ms |
112544 KB |
Output is correct |
8 |
Correct |
281 ms |
112584 KB |
Output is correct |
9 |
Correct |
320 ms |
112520 KB |
Output is correct |
10 |
Correct |
23 ms |
27204 KB |
Output is correct |
11 |
Correct |
13 ms |
23860 KB |
Output is correct |
12 |
Correct |
12 ms |
23764 KB |
Output is correct |
13 |
Correct |
657 ms |
124364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
13 ms |
23804 KB |
Output is correct |
3 |
Correct |
12 ms |
23780 KB |
Output is correct |
4 |
Correct |
13 ms |
23752 KB |
Output is correct |
5 |
Correct |
12 ms |
23744 KB |
Output is correct |
6 |
Correct |
13 ms |
23764 KB |
Output is correct |
7 |
Correct |
13 ms |
23748 KB |
Output is correct |
8 |
Correct |
13 ms |
23796 KB |
Output is correct |
9 |
Correct |
14 ms |
23792 KB |
Output is correct |
10 |
Correct |
12 ms |
23764 KB |
Output is correct |
11 |
Correct |
14 ms |
23764 KB |
Output is correct |
12 |
Correct |
13 ms |
23832 KB |
Output is correct |
13 |
Correct |
13 ms |
23800 KB |
Output is correct |
14 |
Correct |
17 ms |
23712 KB |
Output is correct |
15 |
Correct |
16 ms |
23800 KB |
Output is correct |
16 |
Correct |
13 ms |
23764 KB |
Output is correct |
17 |
Correct |
16 ms |
23800 KB |
Output is correct |
18 |
Correct |
13 ms |
23764 KB |
Output is correct |
19 |
Correct |
13 ms |
23836 KB |
Output is correct |
20 |
Correct |
14 ms |
23756 KB |
Output is correct |
21 |
Correct |
13 ms |
23764 KB |
Output is correct |
22 |
Correct |
15 ms |
24048 KB |
Output is correct |
23 |
Correct |
12 ms |
23804 KB |
Output is correct |
24 |
Correct |
13 ms |
23764 KB |
Output is correct |
25 |
Correct |
14 ms |
23844 KB |
Output is correct |
26 |
Correct |
26 ms |
27232 KB |
Output is correct |
27 |
Correct |
22 ms |
26836 KB |
Output is correct |
28 |
Correct |
22 ms |
26848 KB |
Output is correct |
29 |
Correct |
26 ms |
27268 KB |
Output is correct |
30 |
Correct |
26 ms |
27300 KB |
Output is correct |
31 |
Correct |
183 ms |
39244 KB |
Output is correct |
32 |
Correct |
25 ms |
27220 KB |
Output is correct |
33 |
Correct |
24 ms |
27244 KB |
Output is correct |
34 |
Correct |
29 ms |
27500 KB |
Output is correct |
35 |
Correct |
235 ms |
40628 KB |
Output is correct |
36 |
Correct |
16 ms |
26324 KB |
Output is correct |
37 |
Correct |
28 ms |
27164 KB |
Output is correct |
38 |
Correct |
23 ms |
26856 KB |
Output is correct |
39 |
Correct |
21 ms |
26640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
13 ms |
23804 KB |
Output is correct |
3 |
Correct |
12 ms |
23780 KB |
Output is correct |
4 |
Correct |
13 ms |
23752 KB |
Output is correct |
5 |
Correct |
12 ms |
23744 KB |
Output is correct |
6 |
Correct |
13 ms |
23764 KB |
Output is correct |
7 |
Correct |
13 ms |
23748 KB |
Output is correct |
8 |
Correct |
13 ms |
23796 KB |
Output is correct |
9 |
Correct |
14 ms |
23792 KB |
Output is correct |
10 |
Correct |
12 ms |
23764 KB |
Output is correct |
11 |
Correct |
14 ms |
23764 KB |
Output is correct |
12 |
Correct |
13 ms |
23832 KB |
Output is correct |
13 |
Correct |
13 ms |
23800 KB |
Output is correct |
14 |
Correct |
17 ms |
23712 KB |
Output is correct |
15 |
Correct |
16 ms |
23800 KB |
Output is correct |
16 |
Correct |
13 ms |
23764 KB |
Output is correct |
17 |
Correct |
16 ms |
23800 KB |
Output is correct |
18 |
Correct |
13 ms |
23764 KB |
Output is correct |
19 |
Correct |
13 ms |
23836 KB |
Output is correct |
20 |
Correct |
14 ms |
23756 KB |
Output is correct |
21 |
Correct |
13 ms |
23764 KB |
Output is correct |
22 |
Correct |
15 ms |
24048 KB |
Output is correct |
23 |
Correct |
12 ms |
23804 KB |
Output is correct |
24 |
Correct |
13 ms |
23764 KB |
Output is correct |
25 |
Correct |
14 ms |
23844 KB |
Output is correct |
26 |
Correct |
15 ms |
23704 KB |
Output is correct |
27 |
Correct |
14 ms |
23764 KB |
Output is correct |
28 |
Correct |
15 ms |
23800 KB |
Output is correct |
29 |
Correct |
16 ms |
23732 KB |
Output is correct |
30 |
Correct |
282 ms |
112616 KB |
Output is correct |
31 |
Correct |
309 ms |
112612 KB |
Output is correct |
32 |
Correct |
330 ms |
112544 KB |
Output is correct |
33 |
Correct |
281 ms |
112584 KB |
Output is correct |
34 |
Correct |
320 ms |
112520 KB |
Output is correct |
35 |
Correct |
23 ms |
27204 KB |
Output is correct |
36 |
Correct |
13 ms |
23860 KB |
Output is correct |
37 |
Correct |
12 ms |
23764 KB |
Output is correct |
38 |
Correct |
657 ms |
124364 KB |
Output is correct |
39 |
Correct |
26 ms |
27232 KB |
Output is correct |
40 |
Correct |
22 ms |
26836 KB |
Output is correct |
41 |
Correct |
22 ms |
26848 KB |
Output is correct |
42 |
Correct |
26 ms |
27268 KB |
Output is correct |
43 |
Correct |
26 ms |
27300 KB |
Output is correct |
44 |
Correct |
183 ms |
39244 KB |
Output is correct |
45 |
Correct |
25 ms |
27220 KB |
Output is correct |
46 |
Correct |
24 ms |
27244 KB |
Output is correct |
47 |
Correct |
29 ms |
27500 KB |
Output is correct |
48 |
Correct |
235 ms |
40628 KB |
Output is correct |
49 |
Correct |
16 ms |
26324 KB |
Output is correct |
50 |
Correct |
28 ms |
27164 KB |
Output is correct |
51 |
Correct |
23 ms |
26856 KB |
Output is correct |
52 |
Correct |
21 ms |
26640 KB |
Output is correct |
53 |
Correct |
342 ms |
101272 KB |
Output is correct |
54 |
Correct |
364 ms |
101200 KB |
Output is correct |
55 |
Correct |
528 ms |
113176 KB |
Output is correct |
56 |
Correct |
559 ms |
113196 KB |
Output is correct |
57 |
Correct |
297 ms |
112580 KB |
Output is correct |
58 |
Correct |
283 ms |
112624 KB |
Output is correct |
59 |
Correct |
291 ms |
112596 KB |
Output is correct |
60 |
Correct |
637 ms |
117928 KB |
Output is correct |
61 |
Correct |
95 ms |
86388 KB |
Output is correct |
62 |
Correct |
533 ms |
111040 KB |
Output is correct |
63 |
Correct |
344 ms |
103564 KB |
Output is correct |
64 |
Correct |
292 ms |
95312 KB |
Output is correct |