#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=5e5+5, mod=1e9+7;
int N,M;
vector<pair<int,int>> open[MX], close[MX];
ll dp[MX][26], sdp[MX][26];
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin>>N>>M;
for(int i=0;i<M;i++) {
int a,b;
cin>>a>>b;
if(a<b) {
open[a].push_back({b,1}); // s_{i-1} > s{i}
close[b].push_back({a,1});
} else {
// a > b
open[b].push_back({a,0}); // s_{i-1} < s{i}
close[a].push_back({b,0});
}
}
for(int c=0;c<26;c++) dp[1][c]=1, sdp[1][c]=1;
multiset<int> st[2];
st[0].insert(0);
st[1].insert(0);
for(auto [j,t]:open[1]) st[t].insert(1);
for(int i=2;i<=N;i++) {
int p=*st[0].rbegin();
int q=*st[1].rbegin();
// [max(p,q)+1, i] any value bcs alrdy solved
// [min(p,q)+1, max(p,q)] put appropriate value
if(p<=q) {
ll cur=0;
for(int c=0;c<26;c++) {
dp[i][c]+=cur;
dp[i][c]%=mod;
cur+=sdp[max(p,q)][c];
cur-=sdp[min(p,q)][c];
cur+=mod;
cur%=mod;
}
}
if(p>=q) {
ll cur=0;
for(int c=25;c>=0;c--) {
dp[i][c]+=cur;
dp[i][c]%=mod;
cur+=sdp[max(p,q)][c];
cur-=sdp[min(p,q)][c];
cur+=mod;
cur%=mod;
}
}
ll cur=0;
for(int c=0;c<26;c++) {
dp[i][c]+=cur;
dp[i][c]%=mod;
cur+=sdp[i-1][c];
cur-=sdp[max(p,q)][c];
cur+=mod;
cur%=mod;
}
cur=0;
for(int c=25;c>=0;c--) {
dp[i][c]+=cur;
dp[i][c]%=mod;
cur+=sdp[i-1][c];
cur-=sdp[max(p,q)][c];
cur+=mod;
cur%=mod;
}
for(int c=0;c<26;c++) {
sdp[i][c]=sdp[i-1][c]+dp[i][c];
sdp[i][c]%=mod;
}
for(auto [j,t]:open[i]) st[t].insert(i);
for(auto [j,t]:close[i]) {
st[t].erase(st[t].find(j));
}
}
ll ans=0;
for(int c=0;c<26;c++) {
ans+=sdp[N][c];
ans%=mod;
}
cout<<ans<<'\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
25948 KB |
Output is correct |
2 |
Correct |
6 ms |
25948 KB |
Output is correct |
3 |
Correct |
7 ms |
25948 KB |
Output is correct |
4 |
Correct |
8 ms |
26036 KB |
Output is correct |
5 |
Correct |
7 ms |
26200 KB |
Output is correct |
6 |
Correct |
6 ms |
25948 KB |
Output is correct |
7 |
Correct |
7 ms |
25948 KB |
Output is correct |
8 |
Correct |
7 ms |
26036 KB |
Output is correct |
9 |
Correct |
6 ms |
26204 KB |
Output is correct |
10 |
Correct |
6 ms |
26192 KB |
Output is correct |
11 |
Correct |
6 ms |
25948 KB |
Output is correct |
12 |
Correct |
6 ms |
25948 KB |
Output is correct |
13 |
Correct |
7 ms |
25992 KB |
Output is correct |
14 |
Correct |
6 ms |
25944 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
25948 KB |
Output is correct |
2 |
Correct |
6 ms |
25948 KB |
Output is correct |
3 |
Correct |
7 ms |
25948 KB |
Output is correct |
4 |
Correct |
8 ms |
26036 KB |
Output is correct |
5 |
Correct |
7 ms |
26200 KB |
Output is correct |
6 |
Correct |
6 ms |
25948 KB |
Output is correct |
7 |
Correct |
7 ms |
25948 KB |
Output is correct |
8 |
Correct |
7 ms |
26036 KB |
Output is correct |
9 |
Correct |
6 ms |
26204 KB |
Output is correct |
10 |
Correct |
6 ms |
26192 KB |
Output is correct |
11 |
Correct |
6 ms |
25948 KB |
Output is correct |
12 |
Correct |
6 ms |
25948 KB |
Output is correct |
13 |
Correct |
7 ms |
25992 KB |
Output is correct |
14 |
Correct |
6 ms |
25944 KB |
Output is correct |
15 |
Correct |
6 ms |
26204 KB |
Output is correct |
16 |
Correct |
6 ms |
26204 KB |
Output is correct |
17 |
Correct |
6 ms |
26204 KB |
Output is correct |
18 |
Correct |
6 ms |
26204 KB |
Output is correct |
19 |
Correct |
6 ms |
26204 KB |
Output is correct |
20 |
Correct |
8 ms |
26456 KB |
Output is correct |
21 |
Correct |
6 ms |
26200 KB |
Output is correct |
22 |
Correct |
10 ms |
26716 KB |
Output is correct |
23 |
Correct |
6 ms |
26204 KB |
Output is correct |
24 |
Correct |
6 ms |
26204 KB |
Output is correct |
25 |
Correct |
6 ms |
26196 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
25948 KB |
Output is correct |
2 |
Correct |
7 ms |
25944 KB |
Output is correct |
3 |
Correct |
6 ms |
25948 KB |
Output is correct |
4 |
Correct |
6 ms |
25948 KB |
Output is correct |
5 |
Correct |
413 ms |
265396 KB |
Output is correct |
6 |
Correct |
413 ms |
265276 KB |
Output is correct |
7 |
Correct |
379 ms |
265288 KB |
Output is correct |
8 |
Correct |
382 ms |
265236 KB |
Output is correct |
9 |
Correct |
394 ms |
265232 KB |
Output is correct |
10 |
Correct |
21 ms |
34908 KB |
Output is correct |
11 |
Correct |
6 ms |
26204 KB |
Output is correct |
12 |
Correct |
6 ms |
26200 KB |
Output is correct |
13 |
Correct |
967 ms |
266432 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
25948 KB |
Output is correct |
2 |
Correct |
6 ms |
25948 KB |
Output is correct |
3 |
Correct |
7 ms |
25948 KB |
Output is correct |
4 |
Correct |
8 ms |
26036 KB |
Output is correct |
5 |
Correct |
7 ms |
26200 KB |
Output is correct |
6 |
Correct |
6 ms |
25948 KB |
Output is correct |
7 |
Correct |
7 ms |
25948 KB |
Output is correct |
8 |
Correct |
7 ms |
26036 KB |
Output is correct |
9 |
Correct |
6 ms |
26204 KB |
Output is correct |
10 |
Correct |
6 ms |
26192 KB |
Output is correct |
11 |
Correct |
6 ms |
25948 KB |
Output is correct |
12 |
Correct |
6 ms |
25948 KB |
Output is correct |
13 |
Correct |
7 ms |
25992 KB |
Output is correct |
14 |
Correct |
6 ms |
25944 KB |
Output is correct |
15 |
Correct |
6 ms |
26204 KB |
Output is correct |
16 |
Correct |
6 ms |
26204 KB |
Output is correct |
17 |
Correct |
6 ms |
26204 KB |
Output is correct |
18 |
Correct |
6 ms |
26204 KB |
Output is correct |
19 |
Correct |
6 ms |
26204 KB |
Output is correct |
20 |
Correct |
8 ms |
26456 KB |
Output is correct |
21 |
Correct |
6 ms |
26200 KB |
Output is correct |
22 |
Correct |
10 ms |
26716 KB |
Output is correct |
23 |
Correct |
6 ms |
26204 KB |
Output is correct |
24 |
Correct |
6 ms |
26204 KB |
Output is correct |
25 |
Correct |
6 ms |
26196 KB |
Output is correct |
26 |
Correct |
21 ms |
34904 KB |
Output is correct |
27 |
Correct |
23 ms |
34392 KB |
Output is correct |
28 |
Correct |
21 ms |
34112 KB |
Output is correct |
29 |
Correct |
27 ms |
34648 KB |
Output is correct |
30 |
Correct |
26 ms |
34600 KB |
Output is correct |
31 |
Correct |
303 ms |
51756 KB |
Output is correct |
32 |
Correct |
21 ms |
34908 KB |
Output is correct |
33 |
Correct |
22 ms |
34860 KB |
Output is correct |
34 |
Correct |
27 ms |
34908 KB |
Output is correct |
35 |
Correct |
445 ms |
62496 KB |
Output is correct |
36 |
Correct |
18 ms |
33372 KB |
Output is correct |
37 |
Correct |
29 ms |
34640 KB |
Output is correct |
38 |
Correct |
22 ms |
34212 KB |
Output is correct |
39 |
Correct |
19 ms |
33912 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
25948 KB |
Output is correct |
2 |
Correct |
6 ms |
25948 KB |
Output is correct |
3 |
Correct |
7 ms |
25948 KB |
Output is correct |
4 |
Correct |
8 ms |
26036 KB |
Output is correct |
5 |
Correct |
7 ms |
26200 KB |
Output is correct |
6 |
Correct |
6 ms |
25948 KB |
Output is correct |
7 |
Correct |
7 ms |
25948 KB |
Output is correct |
8 |
Correct |
7 ms |
26036 KB |
Output is correct |
9 |
Correct |
6 ms |
26204 KB |
Output is correct |
10 |
Correct |
6 ms |
26192 KB |
Output is correct |
11 |
Correct |
6 ms |
25948 KB |
Output is correct |
12 |
Correct |
6 ms |
25948 KB |
Output is correct |
13 |
Correct |
7 ms |
25992 KB |
Output is correct |
14 |
Correct |
6 ms |
25944 KB |
Output is correct |
15 |
Correct |
6 ms |
26204 KB |
Output is correct |
16 |
Correct |
6 ms |
26204 KB |
Output is correct |
17 |
Correct |
6 ms |
26204 KB |
Output is correct |
18 |
Correct |
6 ms |
26204 KB |
Output is correct |
19 |
Correct |
6 ms |
26204 KB |
Output is correct |
20 |
Correct |
8 ms |
26456 KB |
Output is correct |
21 |
Correct |
6 ms |
26200 KB |
Output is correct |
22 |
Correct |
10 ms |
26716 KB |
Output is correct |
23 |
Correct |
6 ms |
26204 KB |
Output is correct |
24 |
Correct |
6 ms |
26204 KB |
Output is correct |
25 |
Correct |
6 ms |
26196 KB |
Output is correct |
26 |
Correct |
6 ms |
25948 KB |
Output is correct |
27 |
Correct |
7 ms |
25944 KB |
Output is correct |
28 |
Correct |
6 ms |
25948 KB |
Output is correct |
29 |
Correct |
6 ms |
25948 KB |
Output is correct |
30 |
Correct |
413 ms |
265396 KB |
Output is correct |
31 |
Correct |
413 ms |
265276 KB |
Output is correct |
32 |
Correct |
379 ms |
265288 KB |
Output is correct |
33 |
Correct |
382 ms |
265236 KB |
Output is correct |
34 |
Correct |
394 ms |
265232 KB |
Output is correct |
35 |
Correct |
21 ms |
34908 KB |
Output is correct |
36 |
Correct |
6 ms |
26204 KB |
Output is correct |
37 |
Correct |
6 ms |
26200 KB |
Output is correct |
38 |
Correct |
967 ms |
266432 KB |
Output is correct |
39 |
Correct |
21 ms |
34904 KB |
Output is correct |
40 |
Correct |
23 ms |
34392 KB |
Output is correct |
41 |
Correct |
21 ms |
34112 KB |
Output is correct |
42 |
Correct |
27 ms |
34648 KB |
Output is correct |
43 |
Correct |
26 ms |
34600 KB |
Output is correct |
44 |
Correct |
303 ms |
51756 KB |
Output is correct |
45 |
Correct |
21 ms |
34908 KB |
Output is correct |
46 |
Correct |
22 ms |
34860 KB |
Output is correct |
47 |
Correct |
27 ms |
34908 KB |
Output is correct |
48 |
Correct |
445 ms |
62496 KB |
Output is correct |
49 |
Correct |
18 ms |
33372 KB |
Output is correct |
50 |
Correct |
29 ms |
34640 KB |
Output is correct |
51 |
Correct |
22 ms |
34212 KB |
Output is correct |
52 |
Correct |
19 ms |
33912 KB |
Output is correct |
53 |
Correct |
497 ms |
248460 KB |
Output is correct |
54 |
Correct |
495 ms |
248300 KB |
Output is correct |
55 |
Correct |
800 ms |
260556 KB |
Output is correct |
56 |
Correct |
786 ms |
260516 KB |
Output is correct |
57 |
Correct |
376 ms |
265552 KB |
Output is correct |
58 |
Correct |
376 ms |
265300 KB |
Output is correct |
59 |
Correct |
402 ms |
265296 KB |
Output is correct |
60 |
Correct |
962 ms |
265520 KB |
Output is correct |
61 |
Correct |
293 ms |
227408 KB |
Output is correct |
62 |
Correct |
755 ms |
257520 KB |
Output is correct |
63 |
Correct |
573 ms |
248536 KB |
Output is correct |
64 |
Correct |
408 ms |
238656 KB |
Output is correct |