#include <bits/stdc++.h>
#define f first
#define s second
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define pb push_back
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
#define fast_resp ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<int,ll> pil;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int M=1e9+7;
const int N=5e5+1;
void add(int &a,int b){
a+=b;
if(a>=M) a-=M;
else if(a<0) a+=M;
}
int mult(int a,int b){
return 1ll*a*b%M;
}
int dp[N][26];
set<pii> st[2];
vec<array<int,3>> del[N];
vec<array<int,3>> addt[N];
//set<int> st[2];
signed main(){
fast_resp;
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++){
int l,r;
cin>>l>>r;--l;--r;
if(l<r){
++l;addt[l].pb({0,l,i}),del[r+1].pb({0,l,i});
}
else{
if(l==r) continue;
swap(l,r);++l;
addt[l].pb({1,l,i}),del[r+1].pb({1,l,i});
}
}
for(int i=0;i<26;i++) dp[1][i]=1;
for(int i=1;i<n;i++){
for(auto &z : addt[i]) st[z[0]].insert({z[1],z[2]});
for(auto &z : del[i]) st[z[0]].erase({z[1],z[2]});
for(int j=0;j<26;j++){
for(int k=0;k<26;k++){
add(dp[i+1][k],dp[i][j]);
}
}
if(sz(st[0])){
for(int j=0;j<26;j++){
for(int k=j+1;k<26;k++){
add(dp[i+1][j],-dp[st[0].rbegin()->f][k]);
}
}
}
if(sz(st[1])){
for(int j=0;j<26;j++){
for(int k=0;k<j;k++){
add(dp[i+1][j],-dp[st[1].rbegin()->f][k]);
}
}
}
// for(int j=0;j<26;j++){
// cout<<"HEY "<<i+1<<' '<<j<<' '<<dp[i+1][j]<<endl;
// }
}
int ans=0;
for(int j=0;j<26;j++)
add(ans,dp[n][j]);
cout<<ans;
return 0;
}
/*
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23784 KB |
Output is correct |
3 |
Correct |
12 ms |
23720 KB |
Output is correct |
4 |
Correct |
12 ms |
23764 KB |
Output is correct |
5 |
Correct |
15 ms |
23708 KB |
Output is correct |
6 |
Correct |
16 ms |
23764 KB |
Output is correct |
7 |
Correct |
15 ms |
23756 KB |
Output is correct |
8 |
Correct |
13 ms |
23764 KB |
Output is correct |
9 |
Correct |
11 ms |
23808 KB |
Output is correct |
10 |
Correct |
12 ms |
23764 KB |
Output is correct |
11 |
Correct |
12 ms |
23812 KB |
Output is correct |
12 |
Correct |
12 ms |
23816 KB |
Output is correct |
13 |
Correct |
12 ms |
23772 KB |
Output is correct |
14 |
Correct |
17 ms |
23800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23784 KB |
Output is correct |
3 |
Correct |
12 ms |
23720 KB |
Output is correct |
4 |
Correct |
12 ms |
23764 KB |
Output is correct |
5 |
Correct |
15 ms |
23708 KB |
Output is correct |
6 |
Correct |
16 ms |
23764 KB |
Output is correct |
7 |
Correct |
15 ms |
23756 KB |
Output is correct |
8 |
Correct |
13 ms |
23764 KB |
Output is correct |
9 |
Correct |
11 ms |
23808 KB |
Output is correct |
10 |
Correct |
12 ms |
23764 KB |
Output is correct |
11 |
Correct |
12 ms |
23812 KB |
Output is correct |
12 |
Correct |
12 ms |
23816 KB |
Output is correct |
13 |
Correct |
12 ms |
23772 KB |
Output is correct |
14 |
Correct |
17 ms |
23800 KB |
Output is correct |
15 |
Correct |
12 ms |
23764 KB |
Output is correct |
16 |
Correct |
14 ms |
23808 KB |
Output is correct |
17 |
Correct |
16 ms |
23812 KB |
Output is correct |
18 |
Correct |
16 ms |
23824 KB |
Output is correct |
19 |
Correct |
13 ms |
23764 KB |
Output is correct |
20 |
Correct |
12 ms |
23764 KB |
Output is correct |
21 |
Correct |
14 ms |
23816 KB |
Output is correct |
22 |
Correct |
16 ms |
24488 KB |
Output is correct |
23 |
Correct |
12 ms |
23764 KB |
Output is correct |
24 |
Correct |
12 ms |
23764 KB |
Output is correct |
25 |
Correct |
13 ms |
23772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23808 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
12 ms |
23720 KB |
Output is correct |
4 |
Correct |
13 ms |
23764 KB |
Output is correct |
5 |
Correct |
1703 ms |
112680 KB |
Output is correct |
6 |
Correct |
1821 ms |
112600 KB |
Output is correct |
7 |
Correct |
1775 ms |
112176 KB |
Output is correct |
8 |
Correct |
1691 ms |
112276 KB |
Output is correct |
9 |
Correct |
1702 ms |
112548 KB |
Output is correct |
10 |
Correct |
82 ms |
27256 KB |
Output is correct |
11 |
Correct |
14 ms |
23812 KB |
Output is correct |
12 |
Correct |
14 ms |
23776 KB |
Output is correct |
13 |
Correct |
2413 ms |
113964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23784 KB |
Output is correct |
3 |
Correct |
12 ms |
23720 KB |
Output is correct |
4 |
Correct |
12 ms |
23764 KB |
Output is correct |
5 |
Correct |
15 ms |
23708 KB |
Output is correct |
6 |
Correct |
16 ms |
23764 KB |
Output is correct |
7 |
Correct |
15 ms |
23756 KB |
Output is correct |
8 |
Correct |
13 ms |
23764 KB |
Output is correct |
9 |
Correct |
11 ms |
23808 KB |
Output is correct |
10 |
Correct |
12 ms |
23764 KB |
Output is correct |
11 |
Correct |
12 ms |
23812 KB |
Output is correct |
12 |
Correct |
12 ms |
23816 KB |
Output is correct |
13 |
Correct |
12 ms |
23772 KB |
Output is correct |
14 |
Correct |
17 ms |
23800 KB |
Output is correct |
15 |
Correct |
12 ms |
23764 KB |
Output is correct |
16 |
Correct |
14 ms |
23808 KB |
Output is correct |
17 |
Correct |
16 ms |
23812 KB |
Output is correct |
18 |
Correct |
16 ms |
23824 KB |
Output is correct |
19 |
Correct |
13 ms |
23764 KB |
Output is correct |
20 |
Correct |
12 ms |
23764 KB |
Output is correct |
21 |
Correct |
14 ms |
23816 KB |
Output is correct |
22 |
Correct |
16 ms |
24488 KB |
Output is correct |
23 |
Correct |
12 ms |
23764 KB |
Output is correct |
24 |
Correct |
12 ms |
23764 KB |
Output is correct |
25 |
Correct |
13 ms |
23772 KB |
Output is correct |
26 |
Correct |
79 ms |
27200 KB |
Output is correct |
27 |
Correct |
55 ms |
26624 KB |
Output is correct |
28 |
Correct |
59 ms |
26540 KB |
Output is correct |
29 |
Correct |
94 ms |
26996 KB |
Output is correct |
30 |
Correct |
91 ms |
27140 KB |
Output is correct |
31 |
Correct |
540 ms |
49564 KB |
Output is correct |
32 |
Correct |
81 ms |
27148 KB |
Output is correct |
33 |
Correct |
79 ms |
27192 KB |
Output is correct |
34 |
Correct |
85 ms |
27328 KB |
Output is correct |
35 |
Correct |
722 ms |
59104 KB |
Output is correct |
36 |
Correct |
26 ms |
25736 KB |
Output is correct |
37 |
Correct |
91 ms |
26944 KB |
Output is correct |
38 |
Correct |
82 ms |
26624 KB |
Output is correct |
39 |
Correct |
92 ms |
26232 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23784 KB |
Output is correct |
3 |
Correct |
12 ms |
23720 KB |
Output is correct |
4 |
Correct |
12 ms |
23764 KB |
Output is correct |
5 |
Correct |
15 ms |
23708 KB |
Output is correct |
6 |
Correct |
16 ms |
23764 KB |
Output is correct |
7 |
Correct |
15 ms |
23756 KB |
Output is correct |
8 |
Correct |
13 ms |
23764 KB |
Output is correct |
9 |
Correct |
11 ms |
23808 KB |
Output is correct |
10 |
Correct |
12 ms |
23764 KB |
Output is correct |
11 |
Correct |
12 ms |
23812 KB |
Output is correct |
12 |
Correct |
12 ms |
23816 KB |
Output is correct |
13 |
Correct |
12 ms |
23772 KB |
Output is correct |
14 |
Correct |
17 ms |
23800 KB |
Output is correct |
15 |
Correct |
12 ms |
23764 KB |
Output is correct |
16 |
Correct |
14 ms |
23808 KB |
Output is correct |
17 |
Correct |
16 ms |
23812 KB |
Output is correct |
18 |
Correct |
16 ms |
23824 KB |
Output is correct |
19 |
Correct |
13 ms |
23764 KB |
Output is correct |
20 |
Correct |
12 ms |
23764 KB |
Output is correct |
21 |
Correct |
14 ms |
23816 KB |
Output is correct |
22 |
Correct |
16 ms |
24488 KB |
Output is correct |
23 |
Correct |
12 ms |
23764 KB |
Output is correct |
24 |
Correct |
12 ms |
23764 KB |
Output is correct |
25 |
Correct |
13 ms |
23772 KB |
Output is correct |
26 |
Correct |
12 ms |
23808 KB |
Output is correct |
27 |
Correct |
12 ms |
23764 KB |
Output is correct |
28 |
Correct |
12 ms |
23720 KB |
Output is correct |
29 |
Correct |
13 ms |
23764 KB |
Output is correct |
30 |
Correct |
1703 ms |
112680 KB |
Output is correct |
31 |
Correct |
1821 ms |
112600 KB |
Output is correct |
32 |
Correct |
1775 ms |
112176 KB |
Output is correct |
33 |
Correct |
1691 ms |
112276 KB |
Output is correct |
34 |
Correct |
1702 ms |
112548 KB |
Output is correct |
35 |
Correct |
82 ms |
27256 KB |
Output is correct |
36 |
Correct |
14 ms |
23812 KB |
Output is correct |
37 |
Correct |
14 ms |
23776 KB |
Output is correct |
38 |
Correct |
2413 ms |
113964 KB |
Output is correct |
39 |
Correct |
79 ms |
27200 KB |
Output is correct |
40 |
Correct |
55 ms |
26624 KB |
Output is correct |
41 |
Correct |
59 ms |
26540 KB |
Output is correct |
42 |
Correct |
94 ms |
26996 KB |
Output is correct |
43 |
Correct |
91 ms |
27140 KB |
Output is correct |
44 |
Correct |
540 ms |
49564 KB |
Output is correct |
45 |
Correct |
81 ms |
27148 KB |
Output is correct |
46 |
Correct |
79 ms |
27192 KB |
Output is correct |
47 |
Correct |
85 ms |
27328 KB |
Output is correct |
48 |
Correct |
722 ms |
59104 KB |
Output is correct |
49 |
Correct |
26 ms |
25736 KB |
Output is correct |
50 |
Correct |
91 ms |
26944 KB |
Output is correct |
51 |
Correct |
82 ms |
26624 KB |
Output is correct |
52 |
Correct |
92 ms |
26232 KB |
Output is correct |
53 |
Correct |
1898 ms |
95948 KB |
Output is correct |
54 |
Correct |
1318 ms |
95996 KB |
Output is correct |
55 |
Correct |
2440 ms |
102504 KB |
Output is correct |
56 |
Correct |
2251 ms |
109140 KB |
Output is correct |
57 |
Correct |
1645 ms |
112644 KB |
Output is correct |
58 |
Correct |
1702 ms |
109260 KB |
Output is correct |
59 |
Correct |
1721 ms |
106044 KB |
Output is correct |
60 |
Correct |
2421 ms |
110676 KB |
Output is correct |
61 |
Correct |
536 ms |
74652 KB |
Output is correct |
62 |
Correct |
2135 ms |
105576 KB |
Output is correct |
63 |
Correct |
1935 ms |
96208 KB |
Output is correct |
64 |
Correct |
1671 ms |
86168 KB |
Output is correct |