#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
#define all(x) x.begin() , x.end()
typedef long long ll;
typedef pair<ll , ll> pll;
const ll maxn = 5e5 + 17 , md = 1e9 + 7 , inf = 2e16;
ll a[maxn][2];
vector<ll> b[maxn][2];
ll dp[maxn][26] , ps[maxn][26];
set<ll , greater<ll>> s[2];
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
memset(a , -1 , sizeof(a));
ll n , m;
cin>>n>>m;
for(ll i = 0 ; i < m ; i++){
ll l , r;
cin>>l>>r; l--; r--;
bool f = false;
if(l > r){
swap(l , r); f = true;
}
a[l][f] = max(a[l][f] , r);
}
for(ll i = 0 ; i < n ; i++){
if(a[i][0] != -1){
b[a[i][0]][0].push_back(i);
}
if(a[i][1] != -1){
b[a[i][1]][1].push_back(i);
}
}
for(ll j = 0 ; j < 26 ; j++){
ps[0][j] = dp[0][j] = 1;
}
s[0].insert(-1); s[1].insert(-1);
for(ll i = 0 ; i < n - 1 ; i++){
for(ll k = 0 ; k < 26 ; k++){
dp[i][k] %= md;
}
if(i > 0){
for(ll j = 0 ; j < 26 ; j++){
ps[i][j] = ps[i - 1][j] + dp[i][j];
ps[i][j] -= (ps[i][j] >= md) * md;
}
}
if(a[i][0] != -1){
s[0].insert(i);
}
if(a[i][1] != -1){
s[1].insert(i);
}
for(ll c = 0 ; c < 2 ; c++){
for(auto k : b[i][c]){
s[c].erase(k);
}
}
ll j[] = {*s[0].begin() , *s[1].begin()};
for(ll k = 0 ; k < 26 ; k++){
ll h = 0;
h = ps[i][k] - (j[0] == -1 ? 0 : ps[j[0]][k]);
h += (h < 0) * md;
for(ll t = 0 ; t < k ; t++){
dp[i + 1][t] += h;
}
h = ps[i][k] - (j[1] == -1 ? 0 : ps[j[1]][k]);
h += (h < 0) * md;
for(ll t = k + 1 ; t < 26 ; t++){
dp[i + 1][t] += h;
}
}
}
ll ans = 0;
for(ll i = 0 ; i < n ; i++){
for(ll k = 0 ; k < 26 ; k++){
ans += dp[i][k];
}
ans %= md;
}
ans %= md;
cout<<ans<<'\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
31648 KB |
Output is correct |
2 |
Correct |
18 ms |
31572 KB |
Output is correct |
3 |
Correct |
18 ms |
31648 KB |
Output is correct |
4 |
Correct |
15 ms |
31588 KB |
Output is correct |
5 |
Correct |
16 ms |
31652 KB |
Output is correct |
6 |
Correct |
18 ms |
31548 KB |
Output is correct |
7 |
Correct |
19 ms |
31572 KB |
Output is correct |
8 |
Correct |
18 ms |
31648 KB |
Output is correct |
9 |
Correct |
16 ms |
31572 KB |
Output is correct |
10 |
Correct |
18 ms |
31652 KB |
Output is correct |
11 |
Correct |
15 ms |
31628 KB |
Output is correct |
12 |
Correct |
15 ms |
31532 KB |
Output is correct |
13 |
Correct |
17 ms |
31524 KB |
Output is correct |
14 |
Correct |
16 ms |
31572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
31648 KB |
Output is correct |
2 |
Correct |
18 ms |
31572 KB |
Output is correct |
3 |
Correct |
18 ms |
31648 KB |
Output is correct |
4 |
Correct |
15 ms |
31588 KB |
Output is correct |
5 |
Correct |
16 ms |
31652 KB |
Output is correct |
6 |
Correct |
18 ms |
31548 KB |
Output is correct |
7 |
Correct |
19 ms |
31572 KB |
Output is correct |
8 |
Correct |
18 ms |
31648 KB |
Output is correct |
9 |
Correct |
16 ms |
31572 KB |
Output is correct |
10 |
Correct |
18 ms |
31652 KB |
Output is correct |
11 |
Correct |
15 ms |
31628 KB |
Output is correct |
12 |
Correct |
15 ms |
31532 KB |
Output is correct |
13 |
Correct |
17 ms |
31524 KB |
Output is correct |
14 |
Correct |
16 ms |
31572 KB |
Output is correct |
15 |
Correct |
15 ms |
31644 KB |
Output is correct |
16 |
Correct |
15 ms |
31708 KB |
Output is correct |
17 |
Correct |
18 ms |
31700 KB |
Output is correct |
18 |
Correct |
16 ms |
31700 KB |
Output is correct |
19 |
Correct |
16 ms |
31660 KB |
Output is correct |
20 |
Correct |
17 ms |
31724 KB |
Output is correct |
21 |
Correct |
16 ms |
31636 KB |
Output is correct |
22 |
Correct |
16 ms |
31700 KB |
Output is correct |
23 |
Correct |
17 ms |
31712 KB |
Output is correct |
24 |
Correct |
16 ms |
31700 KB |
Output is correct |
25 |
Correct |
17 ms |
31696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
31580 KB |
Output is correct |
2 |
Correct |
16 ms |
31620 KB |
Output is correct |
3 |
Correct |
15 ms |
31572 KB |
Output is correct |
4 |
Correct |
15 ms |
31528 KB |
Output is correct |
5 |
Correct |
392 ms |
250760 KB |
Output is correct |
6 |
Correct |
403 ms |
257320 KB |
Output is correct |
7 |
Correct |
401 ms |
257540 KB |
Output is correct |
8 |
Correct |
425 ms |
257428 KB |
Output is correct |
9 |
Correct |
386 ms |
257504 KB |
Output is correct |
10 |
Correct |
29 ms |
40524 KB |
Output is correct |
11 |
Correct |
15 ms |
31620 KB |
Output is correct |
12 |
Correct |
15 ms |
31640 KB |
Output is correct |
13 |
Correct |
991 ms |
269068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
31648 KB |
Output is correct |
2 |
Correct |
18 ms |
31572 KB |
Output is correct |
3 |
Correct |
18 ms |
31648 KB |
Output is correct |
4 |
Correct |
15 ms |
31588 KB |
Output is correct |
5 |
Correct |
16 ms |
31652 KB |
Output is correct |
6 |
Correct |
18 ms |
31548 KB |
Output is correct |
7 |
Correct |
19 ms |
31572 KB |
Output is correct |
8 |
Correct |
18 ms |
31648 KB |
Output is correct |
9 |
Correct |
16 ms |
31572 KB |
Output is correct |
10 |
Correct |
18 ms |
31652 KB |
Output is correct |
11 |
Correct |
15 ms |
31628 KB |
Output is correct |
12 |
Correct |
15 ms |
31532 KB |
Output is correct |
13 |
Correct |
17 ms |
31524 KB |
Output is correct |
14 |
Correct |
16 ms |
31572 KB |
Output is correct |
15 |
Correct |
15 ms |
31644 KB |
Output is correct |
16 |
Correct |
15 ms |
31708 KB |
Output is correct |
17 |
Correct |
18 ms |
31700 KB |
Output is correct |
18 |
Correct |
16 ms |
31700 KB |
Output is correct |
19 |
Correct |
16 ms |
31660 KB |
Output is correct |
20 |
Correct |
17 ms |
31724 KB |
Output is correct |
21 |
Correct |
16 ms |
31636 KB |
Output is correct |
22 |
Correct |
16 ms |
31700 KB |
Output is correct |
23 |
Correct |
17 ms |
31712 KB |
Output is correct |
24 |
Correct |
16 ms |
31700 KB |
Output is correct |
25 |
Correct |
17 ms |
31696 KB |
Output is correct |
26 |
Correct |
30 ms |
40620 KB |
Output is correct |
27 |
Correct |
38 ms |
40340 KB |
Output is correct |
28 |
Correct |
38 ms |
40220 KB |
Output is correct |
29 |
Correct |
37 ms |
40576 KB |
Output is correct |
30 |
Correct |
38 ms |
40524 KB |
Output is correct |
31 |
Correct |
111 ms |
45896 KB |
Output is correct |
32 |
Correct |
33 ms |
40564 KB |
Output is correct |
33 |
Correct |
29 ms |
40660 KB |
Output is correct |
34 |
Correct |
35 ms |
40672 KB |
Output is correct |
35 |
Correct |
126 ms |
47088 KB |
Output is correct |
36 |
Correct |
28 ms |
39660 KB |
Output is correct |
37 |
Correct |
36 ms |
40524 KB |
Output is correct |
38 |
Correct |
33 ms |
40308 KB |
Output is correct |
39 |
Correct |
34 ms |
40052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
31648 KB |
Output is correct |
2 |
Correct |
18 ms |
31572 KB |
Output is correct |
3 |
Correct |
18 ms |
31648 KB |
Output is correct |
4 |
Correct |
15 ms |
31588 KB |
Output is correct |
5 |
Correct |
16 ms |
31652 KB |
Output is correct |
6 |
Correct |
18 ms |
31548 KB |
Output is correct |
7 |
Correct |
19 ms |
31572 KB |
Output is correct |
8 |
Correct |
18 ms |
31648 KB |
Output is correct |
9 |
Correct |
16 ms |
31572 KB |
Output is correct |
10 |
Correct |
18 ms |
31652 KB |
Output is correct |
11 |
Correct |
15 ms |
31628 KB |
Output is correct |
12 |
Correct |
15 ms |
31532 KB |
Output is correct |
13 |
Correct |
17 ms |
31524 KB |
Output is correct |
14 |
Correct |
16 ms |
31572 KB |
Output is correct |
15 |
Correct |
15 ms |
31644 KB |
Output is correct |
16 |
Correct |
15 ms |
31708 KB |
Output is correct |
17 |
Correct |
18 ms |
31700 KB |
Output is correct |
18 |
Correct |
16 ms |
31700 KB |
Output is correct |
19 |
Correct |
16 ms |
31660 KB |
Output is correct |
20 |
Correct |
17 ms |
31724 KB |
Output is correct |
21 |
Correct |
16 ms |
31636 KB |
Output is correct |
22 |
Correct |
16 ms |
31700 KB |
Output is correct |
23 |
Correct |
17 ms |
31712 KB |
Output is correct |
24 |
Correct |
16 ms |
31700 KB |
Output is correct |
25 |
Correct |
17 ms |
31696 KB |
Output is correct |
26 |
Correct |
19 ms |
31580 KB |
Output is correct |
27 |
Correct |
16 ms |
31620 KB |
Output is correct |
28 |
Correct |
15 ms |
31572 KB |
Output is correct |
29 |
Correct |
15 ms |
31528 KB |
Output is correct |
30 |
Correct |
392 ms |
250760 KB |
Output is correct |
31 |
Correct |
403 ms |
257320 KB |
Output is correct |
32 |
Correct |
401 ms |
257540 KB |
Output is correct |
33 |
Correct |
425 ms |
257428 KB |
Output is correct |
34 |
Correct |
386 ms |
257504 KB |
Output is correct |
35 |
Correct |
29 ms |
40524 KB |
Output is correct |
36 |
Correct |
15 ms |
31620 KB |
Output is correct |
37 |
Correct |
15 ms |
31640 KB |
Output is correct |
38 |
Correct |
991 ms |
269068 KB |
Output is correct |
39 |
Correct |
30 ms |
40620 KB |
Output is correct |
40 |
Correct |
38 ms |
40340 KB |
Output is correct |
41 |
Correct |
38 ms |
40220 KB |
Output is correct |
42 |
Correct |
37 ms |
40576 KB |
Output is correct |
43 |
Correct |
38 ms |
40524 KB |
Output is correct |
44 |
Correct |
111 ms |
45896 KB |
Output is correct |
45 |
Correct |
33 ms |
40564 KB |
Output is correct |
46 |
Correct |
29 ms |
40660 KB |
Output is correct |
47 |
Correct |
35 ms |
40672 KB |
Output is correct |
48 |
Correct |
126 ms |
47088 KB |
Output is correct |
49 |
Correct |
28 ms |
39660 KB |
Output is correct |
50 |
Correct |
36 ms |
40524 KB |
Output is correct |
51 |
Correct |
33 ms |
40308 KB |
Output is correct |
52 |
Correct |
34 ms |
40052 KB |
Output is correct |
53 |
Correct |
489 ms |
248364 KB |
Output is correct |
54 |
Correct |
577 ms |
248380 KB |
Output is correct |
55 |
Correct |
720 ms |
257272 KB |
Output is correct |
56 |
Correct |
697 ms |
257356 KB |
Output is correct |
57 |
Correct |
416 ms |
257392 KB |
Output is correct |
58 |
Correct |
416 ms |
257376 KB |
Output is correct |
59 |
Correct |
410 ms |
257396 KB |
Output is correct |
60 |
Correct |
791 ms |
260208 KB |
Output is correct |
61 |
Correct |
274 ms |
235084 KB |
Output is correct |
62 |
Correct |
697 ms |
255180 KB |
Output is correct |
63 |
Correct |
501 ms |
249468 KB |
Output is correct |
64 |
Correct |
401 ms |
242972 KB |
Output is correct |