#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second
#define endl "\n"
const int N = 5e5 + 5, mod = 1e9 + 7; //!
int t, n, dp[N][26];
multiset<int> s[2];
vector<pii> st[N], en[N];
void add(int &a, int b) {
if(b < 0) b += mod;
a += b;
if(a >= mod) a -= mod;
}
void upd(int i) {
for(int j = 0; j < st[i].size(); j++) {
s[st[i][j].f].insert(st[i][j].s);
}
for(int j = 0; j < en[i].size(); j++) {
s[en[i][j].f].erase(s[en[i][j].f].find(en[i][j].s));
}
}
main() {
// ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n, m;
cin >> n >> m;
#define pb push_back
for(int i = 1; i <= m; i++) {
int l, r;
cin >> l >> r;
if(l > r) {
st[r].pb({0, r});
en[l].pb({0, r});
} else {
st[l].pb({1, l});
en[r].pb({1, l});
}
}
for(int j = 0; j < 26; j++) dp[1][j] = 1;
upd(1);
for(int i = 2; i <= n; i++) {
int b = 0, c = 0;
if(s[0].size()) {
b = *--s[0].end();
}
if(s[1].size()) {
c = *--s[1].end();
}
vector<int> p(26), sf(26);
for(int k = 0; k < 26; k++) {
if(k) p[k] = p[k - 1];
add(p[k] , dp[i - 1][k] - dp[b][k]);
}
for(int k = 26 - 1; k >= 0; k--) {
if(k != 25) sf[k] = sf[k + 1];
add(sf[k], dp[i - 1][k] - dp[c][k]);
}
for(int j = 0; j < 26; j++) {
dp[i][j] = dp[i - 1][j];
if(j) add(dp[i][j], p[j - 1]);
if(j != 25) add(dp[i][j], sf[j + 1]);
}
upd(i);
}
int ans = 0;
for(int i = 0; i < 26; i++) add(ans , dp[n][i]);
cout << ans;
}
Compilation message
misspelling.cpp: In function 'void upd(int)':
misspelling.cpp:17:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for(int j = 0; j < st[i].size(); j++) {
| ~~^~~~~~~~~~~~~~
misspelling.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int j = 0; j < en[i].size(); j++) {
| ~~^~~~~~~~~~~~~~
misspelling.cpp: At global scope:
misspelling.cpp:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
24 | main() {
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
12 ms |
23796 KB |
Output is correct |
4 |
Correct |
14 ms |
23720 KB |
Output is correct |
5 |
Correct |
14 ms |
23764 KB |
Output is correct |
6 |
Correct |
13 ms |
23796 KB |
Output is correct |
7 |
Correct |
17 ms |
23764 KB |
Output is correct |
8 |
Correct |
13 ms |
23764 KB |
Output is correct |
9 |
Correct |
17 ms |
23796 KB |
Output is correct |
10 |
Correct |
12 ms |
23764 KB |
Output is correct |
11 |
Correct |
12 ms |
23764 KB |
Output is correct |
12 |
Correct |
12 ms |
23764 KB |
Output is correct |
13 |
Correct |
20 ms |
23744 KB |
Output is correct |
14 |
Correct |
12 ms |
23796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
12 ms |
23796 KB |
Output is correct |
4 |
Correct |
14 ms |
23720 KB |
Output is correct |
5 |
Correct |
14 ms |
23764 KB |
Output is correct |
6 |
Correct |
13 ms |
23796 KB |
Output is correct |
7 |
Correct |
17 ms |
23764 KB |
Output is correct |
8 |
Correct |
13 ms |
23764 KB |
Output is correct |
9 |
Correct |
17 ms |
23796 KB |
Output is correct |
10 |
Correct |
12 ms |
23764 KB |
Output is correct |
11 |
Correct |
12 ms |
23764 KB |
Output is correct |
12 |
Correct |
12 ms |
23764 KB |
Output is correct |
13 |
Correct |
20 ms |
23744 KB |
Output is correct |
14 |
Correct |
12 ms |
23796 KB |
Output is correct |
15 |
Correct |
12 ms |
23820 KB |
Output is correct |
16 |
Correct |
11 ms |
23764 KB |
Output is correct |
17 |
Correct |
12 ms |
23764 KB |
Output is correct |
18 |
Correct |
14 ms |
23828 KB |
Output is correct |
19 |
Correct |
13 ms |
23764 KB |
Output is correct |
20 |
Correct |
12 ms |
23764 KB |
Output is correct |
21 |
Correct |
12 ms |
23804 KB |
Output is correct |
22 |
Correct |
21 ms |
24252 KB |
Output is correct |
23 |
Correct |
14 ms |
23800 KB |
Output is correct |
24 |
Correct |
14 ms |
23780 KB |
Output is correct |
25 |
Correct |
14 ms |
23732 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
13 ms |
23688 KB |
Output is correct |
3 |
Correct |
12 ms |
23712 KB |
Output is correct |
4 |
Correct |
14 ms |
23768 KB |
Output is correct |
5 |
Correct |
543 ms |
105932 KB |
Output is correct |
6 |
Correct |
544 ms |
105888 KB |
Output is correct |
7 |
Correct |
541 ms |
105956 KB |
Output is correct |
8 |
Correct |
524 ms |
105912 KB |
Output is correct |
9 |
Correct |
532 ms |
105848 KB |
Output is correct |
10 |
Correct |
35 ms |
26956 KB |
Output is correct |
11 |
Correct |
13 ms |
23716 KB |
Output is correct |
12 |
Correct |
12 ms |
23764 KB |
Output is correct |
13 |
Correct |
1223 ms |
107200 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
12 ms |
23796 KB |
Output is correct |
4 |
Correct |
14 ms |
23720 KB |
Output is correct |
5 |
Correct |
14 ms |
23764 KB |
Output is correct |
6 |
Correct |
13 ms |
23796 KB |
Output is correct |
7 |
Correct |
17 ms |
23764 KB |
Output is correct |
8 |
Correct |
13 ms |
23764 KB |
Output is correct |
9 |
Correct |
17 ms |
23796 KB |
Output is correct |
10 |
Correct |
12 ms |
23764 KB |
Output is correct |
11 |
Correct |
12 ms |
23764 KB |
Output is correct |
12 |
Correct |
12 ms |
23764 KB |
Output is correct |
13 |
Correct |
20 ms |
23744 KB |
Output is correct |
14 |
Correct |
12 ms |
23796 KB |
Output is correct |
15 |
Correct |
12 ms |
23820 KB |
Output is correct |
16 |
Correct |
11 ms |
23764 KB |
Output is correct |
17 |
Correct |
12 ms |
23764 KB |
Output is correct |
18 |
Correct |
14 ms |
23828 KB |
Output is correct |
19 |
Correct |
13 ms |
23764 KB |
Output is correct |
20 |
Correct |
12 ms |
23764 KB |
Output is correct |
21 |
Correct |
12 ms |
23804 KB |
Output is correct |
22 |
Correct |
21 ms |
24252 KB |
Output is correct |
23 |
Correct |
14 ms |
23800 KB |
Output is correct |
24 |
Correct |
14 ms |
23780 KB |
Output is correct |
25 |
Correct |
14 ms |
23732 KB |
Output is correct |
26 |
Correct |
33 ms |
26948 KB |
Output is correct |
27 |
Correct |
29 ms |
26472 KB |
Output is correct |
28 |
Correct |
38 ms |
26424 KB |
Output is correct |
29 |
Correct |
40 ms |
26804 KB |
Output is correct |
30 |
Correct |
38 ms |
26804 KB |
Output is correct |
31 |
Correct |
557 ms |
38872 KB |
Output is correct |
32 |
Correct |
33 ms |
27044 KB |
Output is correct |
33 |
Correct |
33 ms |
26948 KB |
Output is correct |
34 |
Correct |
41 ms |
26956 KB |
Output is correct |
35 |
Correct |
777 ms |
49504 KB |
Output is correct |
36 |
Correct |
19 ms |
25812 KB |
Output is correct |
37 |
Correct |
34 ms |
26700 KB |
Output is correct |
38 |
Correct |
30 ms |
26516 KB |
Output is correct |
39 |
Correct |
24 ms |
26196 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
12 ms |
23796 KB |
Output is correct |
4 |
Correct |
14 ms |
23720 KB |
Output is correct |
5 |
Correct |
14 ms |
23764 KB |
Output is correct |
6 |
Correct |
13 ms |
23796 KB |
Output is correct |
7 |
Correct |
17 ms |
23764 KB |
Output is correct |
8 |
Correct |
13 ms |
23764 KB |
Output is correct |
9 |
Correct |
17 ms |
23796 KB |
Output is correct |
10 |
Correct |
12 ms |
23764 KB |
Output is correct |
11 |
Correct |
12 ms |
23764 KB |
Output is correct |
12 |
Correct |
12 ms |
23764 KB |
Output is correct |
13 |
Correct |
20 ms |
23744 KB |
Output is correct |
14 |
Correct |
12 ms |
23796 KB |
Output is correct |
15 |
Correct |
12 ms |
23820 KB |
Output is correct |
16 |
Correct |
11 ms |
23764 KB |
Output is correct |
17 |
Correct |
12 ms |
23764 KB |
Output is correct |
18 |
Correct |
14 ms |
23828 KB |
Output is correct |
19 |
Correct |
13 ms |
23764 KB |
Output is correct |
20 |
Correct |
12 ms |
23764 KB |
Output is correct |
21 |
Correct |
12 ms |
23804 KB |
Output is correct |
22 |
Correct |
21 ms |
24252 KB |
Output is correct |
23 |
Correct |
14 ms |
23800 KB |
Output is correct |
24 |
Correct |
14 ms |
23780 KB |
Output is correct |
25 |
Correct |
14 ms |
23732 KB |
Output is correct |
26 |
Correct |
12 ms |
23764 KB |
Output is correct |
27 |
Correct |
13 ms |
23688 KB |
Output is correct |
28 |
Correct |
12 ms |
23712 KB |
Output is correct |
29 |
Correct |
14 ms |
23768 KB |
Output is correct |
30 |
Correct |
543 ms |
105932 KB |
Output is correct |
31 |
Correct |
544 ms |
105888 KB |
Output is correct |
32 |
Correct |
541 ms |
105956 KB |
Output is correct |
33 |
Correct |
524 ms |
105912 KB |
Output is correct |
34 |
Correct |
532 ms |
105848 KB |
Output is correct |
35 |
Correct |
35 ms |
26956 KB |
Output is correct |
36 |
Correct |
13 ms |
23716 KB |
Output is correct |
37 |
Correct |
12 ms |
23764 KB |
Output is correct |
38 |
Correct |
1223 ms |
107200 KB |
Output is correct |
39 |
Correct |
33 ms |
26948 KB |
Output is correct |
40 |
Correct |
29 ms |
26472 KB |
Output is correct |
41 |
Correct |
38 ms |
26424 KB |
Output is correct |
42 |
Correct |
40 ms |
26804 KB |
Output is correct |
43 |
Correct |
38 ms |
26804 KB |
Output is correct |
44 |
Correct |
557 ms |
38872 KB |
Output is correct |
45 |
Correct |
33 ms |
27044 KB |
Output is correct |
46 |
Correct |
33 ms |
26948 KB |
Output is correct |
47 |
Correct |
41 ms |
26956 KB |
Output is correct |
48 |
Correct |
777 ms |
49504 KB |
Output is correct |
49 |
Correct |
19 ms |
25812 KB |
Output is correct |
50 |
Correct |
34 ms |
26700 KB |
Output is correct |
51 |
Correct |
30 ms |
26516 KB |
Output is correct |
52 |
Correct |
24 ms |
26196 KB |
Output is correct |
53 |
Correct |
530 ms |
92380 KB |
Output is correct |
54 |
Correct |
570 ms |
92364 KB |
Output is correct |
55 |
Correct |
952 ms |
101072 KB |
Output is correct |
56 |
Correct |
939 ms |
101200 KB |
Output is correct |
57 |
Correct |
495 ms |
105944 KB |
Output is correct |
58 |
Correct |
505 ms |
105932 KB |
Output is correct |
59 |
Correct |
492 ms |
105876 KB |
Output is correct |
60 |
Correct |
1132 ms |
106188 KB |
Output is correct |
61 |
Correct |
178 ms |
74576 KB |
Output is correct |
62 |
Correct |
862 ms |
99800 KB |
Output is correct |
63 |
Correct |
613 ms |
92548 KB |
Output is correct |
64 |
Correct |
357 ms |
84360 KB |
Output is correct |