#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 6e5 + 5;
const int mod = 1e9 + 7, oo = 1e18 + 7;
int n, q, a[N];
vector<iii> ques;
int dp[N][26];
int pref[N][26], suff[N][26];
set<ii> se[2];
int ck(int i, int j){// ck = 0 -> < , ck = 1 -> >; j < i
/*
bool ck0 = 1, ck1 = 1;
for(auto it : ques){
if(it.fi.fi > j && it.fi.fi <= i && it.fi.se >= i){
ck0 &= (it.se == 0);
ck1 &= (it.se == 1);
}
}
if(!ck0 && !ck1) return -1;
else if(!ck1) return 0;
else if(!ck0) return 1;
else return 2;*/
int temp0 = (se[0].size() ? (*se[0].rbegin()).fi : -oo), temp1 = (se[1].size() ? (*se[1].rbegin()).fi : -oo);
bool ck0 = (temp1 <= j), ck1 = (temp0 <= j);
if(!ck0 && !ck1) return -1;
else if(!ck1) return 0;
else if(!ck0) return 1;
else return 2;
}
vector<ii> que[N];
void add(int &a, int b){
a = (a + b) % mod;
}
int quee(int l, int r, int x){
// cout << l << " " << r << " " << x << " " << pref[r][x] << " " << pref[l - 1][x] << "\n";
if(l > r) return 0;
else if(!l) return pref[r][x];
// cout << l << " " << r << " " << x << " " << pref[r][x] << " " << pref[l - 1][x] << "\n";
return (pref[r][x] - pref[l - 1][x] + mod) % mod;
}
void process(){
cin >> n >> q;
for(int i = 1; i <= q; i++){
int x, y;
cin >> x >> y;
if(x == y) continue;
if(x < y){
ques.pb({{x + 1, y}, 0});
que[x + 1].pb({i - 1, 0});
que[y].pb({i - 1, 1});
}
else{
ques.pb({{y + 1, x}, 1});
que[y + 1].pb({i - 1, 0});
que[x].pb({i - 1, 1});
}
}
for(int i = 0; i < 26; i++) dp[1][i] = pref[1][i] = 1;
for(int i = 2; i <= n; i++){
for(auto it : que[i]){
if(it.se == 0){
se[ques[it.fi].se].insert({ques[it.fi].fi.fi, it.fi});
}
}
int pos0 = (se[0].size() ? (*se[0].rbegin()).fi : -oo), pos1 = (se[1].size() ? (*se[1].rbegin()).fi : -oo);
//cout << pos0 << " " << pos1 << "\n";
/*
for(int j = max(0LL, max(pos0, pos1)); j < i; j++){
for(int k = 0; k < 26; k++){
for(int h = 0; h < k; h++){
add(dp[i][k], dp[j][h]);
}
}
for(int k = 0; k < 26; k++){
for(int h = k + 1; h < 26; h++){
add(dp[i][k], dp[j][h]);
}
}
}*/
int tol = 0;
for(int k = 0; k < 26; k++){
add(dp[i][k], tol);
//cout << tol << "\n";
add(tol, quee(max(0LL, max(pos0, pos1)), i - 1, k));
}
tol = 0;
for(int k = 25; k >= 0; k--){
add(dp[i][k], tol);
add(tol, quee(max(0LL, max(pos0, pos1)), i - 1, k));
}
/*
for(int j = max(0LL, min(pos0, pos1)); j < max(0LL, max(pos0, pos1)); j++){
if(pos0 < pos1){
for(int k = 0; k < 26; k++){
for(int h = k + 1; h < 26; h++) add(dp[i][k], dp[j][h]);
}
}
else{
for(int k = 0; k < 26; k++){
for(int h = 0; h < k; h++) add(dp[i][k], dp[j][h]);
}
}
}*/
if(pos0 < pos1){
tol = 0;
for(int k = 25; k >= 0; k--){
add(dp[i][k], tol);
//cout << tol << "\n";
add(tol, quee(max(0LL, min(pos0, pos1)), max(0LL, max(pos0, pos1)) - 1, k));
}
}
else{
tol = 0;
for(int k = 0; k < 26; k++){
add(dp[i][k], tol);
//cout << tol << "\n";
add(tol, quee(max(0LL, min(pos0, pos1)), max(0LL, max(pos0, pos1)) - 1, k));
}
}
/*
for(int j = 1; j < i; j++){
int temp = ck(i, j);
//cout << i << " " << j << " " << temp << "\n";
//cout << i << " " << j << " " << temp << "\n";
if(temp == 0 || temp == 2){
for(int k = 0; k < 26; k++){
for(int h = 0; h < k; h++){
add(dp[i][k], dp[j][h]);
}
}
}
if(temp == 1 || temp == 2){
for(int k = 0; k < 26; k++){
for(int h = k + 1; h < 26; h++){
add(dp[i][k], dp[j][h]);
}
}
}
}*/
for(auto it : que[i]){
if(it.se == 1){
se[ques[it.fi].se].erase({ques[it.fi].fi.fi, it.fi});
}
}
for(int j = 0; j < 26; j++){
// cout << i << " " << j << " " << dp[i][j] << "\n";
pref[i][j] = pref[i - 1][j];
add(pref[i][j], dp[i][j]);
}
}
int ans = 0;
for(int i = 1; i <= n; i++){
for(int j = 0; j < 26; j++){
add(ans, dp[i][j]);
}
}
cout << ans << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
//freopen("KEK.inp", "r", stdin);
//freopen("KEK.out", "w", stdout);
cin.tie(0);
process();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
14436 KB |
Output is correct |
2 |
Correct |
9 ms |
14420 KB |
Output is correct |
3 |
Correct |
8 ms |
14420 KB |
Output is correct |
4 |
Correct |
8 ms |
14420 KB |
Output is correct |
5 |
Correct |
9 ms |
14420 KB |
Output is correct |
6 |
Correct |
8 ms |
14420 KB |
Output is correct |
7 |
Correct |
8 ms |
14440 KB |
Output is correct |
8 |
Correct |
7 ms |
14420 KB |
Output is correct |
9 |
Correct |
8 ms |
14420 KB |
Output is correct |
10 |
Correct |
7 ms |
14420 KB |
Output is correct |
11 |
Correct |
8 ms |
14420 KB |
Output is correct |
12 |
Correct |
8 ms |
14420 KB |
Output is correct |
13 |
Correct |
8 ms |
14432 KB |
Output is correct |
14 |
Correct |
8 ms |
14420 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
14436 KB |
Output is correct |
2 |
Correct |
9 ms |
14420 KB |
Output is correct |
3 |
Correct |
8 ms |
14420 KB |
Output is correct |
4 |
Correct |
8 ms |
14420 KB |
Output is correct |
5 |
Correct |
9 ms |
14420 KB |
Output is correct |
6 |
Correct |
8 ms |
14420 KB |
Output is correct |
7 |
Correct |
8 ms |
14440 KB |
Output is correct |
8 |
Correct |
7 ms |
14420 KB |
Output is correct |
9 |
Correct |
8 ms |
14420 KB |
Output is correct |
10 |
Correct |
7 ms |
14420 KB |
Output is correct |
11 |
Correct |
8 ms |
14420 KB |
Output is correct |
12 |
Correct |
8 ms |
14420 KB |
Output is correct |
13 |
Correct |
8 ms |
14432 KB |
Output is correct |
14 |
Correct |
8 ms |
14420 KB |
Output is correct |
15 |
Correct |
9 ms |
14420 KB |
Output is correct |
16 |
Correct |
8 ms |
14420 KB |
Output is correct |
17 |
Correct |
9 ms |
14488 KB |
Output is correct |
18 |
Correct |
8 ms |
14548 KB |
Output is correct |
19 |
Correct |
8 ms |
14528 KB |
Output is correct |
20 |
Correct |
8 ms |
14440 KB |
Output is correct |
21 |
Correct |
8 ms |
14548 KB |
Output is correct |
22 |
Correct |
13 ms |
15476 KB |
Output is correct |
23 |
Correct |
7 ms |
14420 KB |
Output is correct |
24 |
Correct |
8 ms |
14420 KB |
Output is correct |
25 |
Correct |
8 ms |
14516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
14432 KB |
Output is correct |
2 |
Correct |
10 ms |
14420 KB |
Output is correct |
3 |
Correct |
7 ms |
14420 KB |
Output is correct |
4 |
Correct |
8 ms |
14416 KB |
Output is correct |
5 |
Correct |
561 ms |
254208 KB |
Output is correct |
6 |
Correct |
574 ms |
261020 KB |
Output is correct |
7 |
Correct |
548 ms |
260832 KB |
Output is correct |
8 |
Correct |
554 ms |
260916 KB |
Output is correct |
9 |
Correct |
625 ms |
260840 KB |
Output is correct |
10 |
Correct |
32 ms |
24248 KB |
Output is correct |
11 |
Correct |
8 ms |
14432 KB |
Output is correct |
12 |
Correct |
8 ms |
14420 KB |
Output is correct |
13 |
Correct |
1426 ms |
277224 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
14436 KB |
Output is correct |
2 |
Correct |
9 ms |
14420 KB |
Output is correct |
3 |
Correct |
8 ms |
14420 KB |
Output is correct |
4 |
Correct |
8 ms |
14420 KB |
Output is correct |
5 |
Correct |
9 ms |
14420 KB |
Output is correct |
6 |
Correct |
8 ms |
14420 KB |
Output is correct |
7 |
Correct |
8 ms |
14440 KB |
Output is correct |
8 |
Correct |
7 ms |
14420 KB |
Output is correct |
9 |
Correct |
8 ms |
14420 KB |
Output is correct |
10 |
Correct |
7 ms |
14420 KB |
Output is correct |
11 |
Correct |
8 ms |
14420 KB |
Output is correct |
12 |
Correct |
8 ms |
14420 KB |
Output is correct |
13 |
Correct |
8 ms |
14432 KB |
Output is correct |
14 |
Correct |
8 ms |
14420 KB |
Output is correct |
15 |
Correct |
9 ms |
14420 KB |
Output is correct |
16 |
Correct |
8 ms |
14420 KB |
Output is correct |
17 |
Correct |
9 ms |
14488 KB |
Output is correct |
18 |
Correct |
8 ms |
14548 KB |
Output is correct |
19 |
Correct |
8 ms |
14528 KB |
Output is correct |
20 |
Correct |
8 ms |
14440 KB |
Output is correct |
21 |
Correct |
8 ms |
14548 KB |
Output is correct |
22 |
Correct |
13 ms |
15476 KB |
Output is correct |
23 |
Correct |
7 ms |
14420 KB |
Output is correct |
24 |
Correct |
8 ms |
14420 KB |
Output is correct |
25 |
Correct |
8 ms |
14516 KB |
Output is correct |
26 |
Correct |
78 ms |
24008 KB |
Output is correct |
27 |
Correct |
31 ms |
23488 KB |
Output is correct |
28 |
Correct |
29 ms |
23584 KB |
Output is correct |
29 |
Correct |
37 ms |
24324 KB |
Output is correct |
30 |
Correct |
35 ms |
24376 KB |
Output is correct |
31 |
Correct |
513 ms |
57948 KB |
Output is correct |
32 |
Correct |
30 ms |
23944 KB |
Output is correct |
33 |
Correct |
30 ms |
23976 KB |
Output is correct |
34 |
Correct |
40 ms |
24720 KB |
Output is correct |
35 |
Correct |
753 ms |
70940 KB |
Output is correct |
36 |
Correct |
22 ms |
22504 KB |
Output is correct |
37 |
Correct |
151 ms |
24148 KB |
Output is correct |
38 |
Correct |
30 ms |
23596 KB |
Output is correct |
39 |
Correct |
26 ms |
23144 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
14436 KB |
Output is correct |
2 |
Correct |
9 ms |
14420 KB |
Output is correct |
3 |
Correct |
8 ms |
14420 KB |
Output is correct |
4 |
Correct |
8 ms |
14420 KB |
Output is correct |
5 |
Correct |
9 ms |
14420 KB |
Output is correct |
6 |
Correct |
8 ms |
14420 KB |
Output is correct |
7 |
Correct |
8 ms |
14440 KB |
Output is correct |
8 |
Correct |
7 ms |
14420 KB |
Output is correct |
9 |
Correct |
8 ms |
14420 KB |
Output is correct |
10 |
Correct |
7 ms |
14420 KB |
Output is correct |
11 |
Correct |
8 ms |
14420 KB |
Output is correct |
12 |
Correct |
8 ms |
14420 KB |
Output is correct |
13 |
Correct |
8 ms |
14432 KB |
Output is correct |
14 |
Correct |
8 ms |
14420 KB |
Output is correct |
15 |
Correct |
9 ms |
14420 KB |
Output is correct |
16 |
Correct |
8 ms |
14420 KB |
Output is correct |
17 |
Correct |
9 ms |
14488 KB |
Output is correct |
18 |
Correct |
8 ms |
14548 KB |
Output is correct |
19 |
Correct |
8 ms |
14528 KB |
Output is correct |
20 |
Correct |
8 ms |
14440 KB |
Output is correct |
21 |
Correct |
8 ms |
14548 KB |
Output is correct |
22 |
Correct |
13 ms |
15476 KB |
Output is correct |
23 |
Correct |
7 ms |
14420 KB |
Output is correct |
24 |
Correct |
8 ms |
14420 KB |
Output is correct |
25 |
Correct |
8 ms |
14516 KB |
Output is correct |
26 |
Correct |
7 ms |
14432 KB |
Output is correct |
27 |
Correct |
10 ms |
14420 KB |
Output is correct |
28 |
Correct |
7 ms |
14420 KB |
Output is correct |
29 |
Correct |
8 ms |
14416 KB |
Output is correct |
30 |
Correct |
561 ms |
254208 KB |
Output is correct |
31 |
Correct |
574 ms |
261020 KB |
Output is correct |
32 |
Correct |
548 ms |
260832 KB |
Output is correct |
33 |
Correct |
554 ms |
260916 KB |
Output is correct |
34 |
Correct |
625 ms |
260840 KB |
Output is correct |
35 |
Correct |
32 ms |
24248 KB |
Output is correct |
36 |
Correct |
8 ms |
14432 KB |
Output is correct |
37 |
Correct |
8 ms |
14420 KB |
Output is correct |
38 |
Correct |
1426 ms |
277224 KB |
Output is correct |
39 |
Correct |
78 ms |
24008 KB |
Output is correct |
40 |
Correct |
31 ms |
23488 KB |
Output is correct |
41 |
Correct |
29 ms |
23584 KB |
Output is correct |
42 |
Correct |
37 ms |
24324 KB |
Output is correct |
43 |
Correct |
35 ms |
24376 KB |
Output is correct |
44 |
Correct |
513 ms |
57948 KB |
Output is correct |
45 |
Correct |
30 ms |
23944 KB |
Output is correct |
46 |
Correct |
30 ms |
23976 KB |
Output is correct |
47 |
Correct |
40 ms |
24720 KB |
Output is correct |
48 |
Correct |
753 ms |
70940 KB |
Output is correct |
49 |
Correct |
22 ms |
22504 KB |
Output is correct |
50 |
Correct |
151 ms |
24148 KB |
Output is correct |
51 |
Correct |
30 ms |
23596 KB |
Output is correct |
52 |
Correct |
26 ms |
23144 KB |
Output is correct |
53 |
Correct |
818 ms |
246716 KB |
Output is correct |
54 |
Correct |
715 ms |
246732 KB |
Output is correct |
55 |
Correct |
1158 ms |
269576 KB |
Output is correct |
56 |
Correct |
1268 ms |
269476 KB |
Output is correct |
57 |
Correct |
552 ms |
260848 KB |
Output is correct |
58 |
Correct |
563 ms |
260836 KB |
Output is correct |
59 |
Correct |
945 ms |
260884 KB |
Output is correct |
60 |
Correct |
1396 ms |
277864 KB |
Output is correct |
61 |
Correct |
357 ms |
217960 KB |
Output is correct |
62 |
Correct |
1197 ms |
263128 KB |
Output is correct |
63 |
Correct |
1089 ms |
248308 KB |
Output is correct |
64 |
Correct |
611 ms |
233428 KB |
Output is correct |