#include<bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define pii pair<int, int>
#define fi first
#define se second
#define mod 1000000007
#define A 26
typedef long long ll;
using namespace std;
struct modular{
int a;
modular(int x = 0){a = x;}
modular operator+(modular t){return {(a+t.a)%mod};}
modular operator-(modular t){return {(a-t.a+mod)%mod};}
void operator+=(modular t){a = (a+t.a)%mod;}
};
int main(){
int n, m;
scanf("%d%d", &n, &m);
vector<set<pii>> s(2);
while(m--){
int a, b;
scanf("%d%d", &a, &b);
if(a < b) s[0].emplace(a, b);
else s[1].emplace(b, a);
}
vector<vector<modular>> dp(n+1, vector<modular>(A, 0));
REP(lit, A) dp[1][lit] = 1;
FOR(pref, 1, n-1) REP(lit, A){
modular t = dp[pref][lit];
auto f = [&](int x){
while(s[x].size()){
auto it = s[x].lower_bound({pref+1, 0});
if(it == s[x].begin()) return 0;
it = prev(it);
if(it->se > pref) return it->fi;
s[x].erase(it);
}
return 0;
};
int dol = f(1);
int gora = f(0);
REP(nowa, A){
int ogr = 0;
if(nowa < lit) ogr = dol;
if(nowa > lit) ogr = gora;
dp[pref+1][nowa] += t-dp[ogr][lit];
}
}
modular wyn = 0;
REP(lit, A) wyn += dp[n][lit];
printf("%d", wyn.a);
}
Compilation message
misspelling.cpp: In function 'int main()':
misspelling.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
misspelling.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
26 | 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 |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 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 |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
4 ms |
724 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 |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
2731 ms |
90264 KB |
Output is correct |
6 |
Correct |
2824 ms |
91468 KB |
Output is correct |
7 |
Correct |
2553 ms |
91468 KB |
Output is correct |
8 |
Correct |
2816 ms |
91536 KB |
Output is correct |
9 |
Correct |
2696 ms |
91516 KB |
Output is correct |
10 |
Correct |
89 ms |
4052 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
2294 ms |
91596 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 |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 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 |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
4 ms |
724 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 |
89 ms |
3796 KB |
Output is correct |
27 |
Correct |
62 ms |
3540 KB |
Output is correct |
28 |
Correct |
71 ms |
3488 KB |
Output is correct |
29 |
Correct |
77 ms |
4052 KB |
Output is correct |
30 |
Correct |
77 ms |
4052 KB |
Output is correct |
31 |
Correct |
441 ms |
27688 KB |
Output is correct |
32 |
Correct |
77 ms |
4052 KB |
Output is correct |
33 |
Correct |
76 ms |
4024 KB |
Output is correct |
34 |
Correct |
76 ms |
4052 KB |
Output is correct |
35 |
Correct |
439 ms |
27632 KB |
Output is correct |
36 |
Correct |
45 ms |
2900 KB |
Output is correct |
37 |
Correct |
72 ms |
3796 KB |
Output is correct |
38 |
Correct |
69 ms |
3540 KB |
Output is correct |
39 |
Correct |
63 ms |
3244 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 |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 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 |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
4 ms |
724 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 |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
0 ms |
212 KB |
Output is correct |
29 |
Correct |
0 ms |
212 KB |
Output is correct |
30 |
Correct |
2731 ms |
90264 KB |
Output is correct |
31 |
Correct |
2824 ms |
91468 KB |
Output is correct |
32 |
Correct |
2553 ms |
91468 KB |
Output is correct |
33 |
Correct |
2816 ms |
91536 KB |
Output is correct |
34 |
Correct |
2696 ms |
91516 KB |
Output is correct |
35 |
Correct |
89 ms |
4052 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
0 ms |
212 KB |
Output is correct |
38 |
Correct |
2294 ms |
91596 KB |
Output is correct |
39 |
Correct |
89 ms |
3796 KB |
Output is correct |
40 |
Correct |
62 ms |
3540 KB |
Output is correct |
41 |
Correct |
71 ms |
3488 KB |
Output is correct |
42 |
Correct |
77 ms |
4052 KB |
Output is correct |
43 |
Correct |
77 ms |
4052 KB |
Output is correct |
44 |
Correct |
441 ms |
27688 KB |
Output is correct |
45 |
Correct |
77 ms |
4052 KB |
Output is correct |
46 |
Correct |
76 ms |
4024 KB |
Output is correct |
47 |
Correct |
76 ms |
4052 KB |
Output is correct |
48 |
Correct |
439 ms |
27632 KB |
Output is correct |
49 |
Correct |
45 ms |
2900 KB |
Output is correct |
50 |
Correct |
72 ms |
3796 KB |
Output is correct |
51 |
Correct |
69 ms |
3540 KB |
Output is correct |
52 |
Correct |
63 ms |
3244 KB |
Output is correct |
53 |
Correct |
2048 ms |
79808 KB |
Output is correct |
54 |
Correct |
1978 ms |
79768 KB |
Output is correct |
55 |
Correct |
2484 ms |
91468 KB |
Output is correct |
56 |
Correct |
2483 ms |
91576 KB |
Output is correct |
57 |
Correct |
2690 ms |
91552 KB |
Output is correct |
58 |
Correct |
2466 ms |
91556 KB |
Output is correct |
59 |
Correct |
2691 ms |
91468 KB |
Output is correct |
60 |
Correct |
2252 ms |
91592 KB |
Output is correct |
61 |
Correct |
1130 ms |
66892 KB |
Output is correct |
62 |
Correct |
2103 ms |
85632 KB |
Output is correct |
63 |
Correct |
1931 ms |
79828 KB |
Output is correct |
64 |
Correct |
1744 ms |
73932 KB |
Output is correct |