#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define f first
#define s second
#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define RREP(i,n) for (int i=n-1;i>=0;--i)
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do( T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT
const int mod = 1e9+7;
const int maxn = 5e5+5;
#define dec DECCCC
int inc[maxn], dec[maxn];
void prune(vector<pii> v, bool doinc) {
for (pii &p : v) {
p.f = -p.f; p.s = -p.s; swap(p.f, p.s);
}
sort(ALL(v), [&](pii a, pii b){return a.s!=b.s?a.s < b.s : a.f < b.f;});
vector<pii> R;
for (pii p : v) {
while (SZ(R) && p.f < R.back().f) {
R.pop_back();
}
if (SZ(R)) MX(p.f, R.back().s+1);
if (p.f <= p.s) {
bug(p.f, p.s);
(doinc?inc:dec)[-p.s] = -p.f;
R.pb({p.f, p.s});
}
}
}
int dpi[maxn][26], dpd[maxn][26];
inline void ADD(int &a, int b) {
a = (a+b)>=mod?a+b-mod:a+b;
}
void eat(int *a, int *b, int tp) { // 1: i eats bigger, 0: eq, -1: i eats smaller
if (tp == 1) {
int tmp = 0;
RREP(j,26) {
ADD(a[j], tmp);
ADD(tmp, b[j]);
}
}else if (tp == -1) {
int tmp = 0;
REP(j,26) {
ADD(a[j], tmp);
ADD(tmp, b[j]);
}
}else{
REP(j,26) {
ADD(a[j], b[j]);
}
}
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0);
bug(1,2);
int n,m; cin>>n>>m;
vector<pii> vinc, vdec;
REP(i,m) {
int a,b; cin>>a>>b; --a; --b;
if (a < b) vinc.pb({a,b-1});
else vdec.pb({b,a-1});
}
memset(inc, -1, sizeof inc);
memset(dec, -1, sizeof dec);
prune(vinc, 1);
prune(vdec, 0);
REP(j,26) dpi[n-1][j]=1;
for (int i = n-2; i>=0; --i) {
bug(i, inc[i], dec[i]);
if (dec[i] == -1) {
eat(dpi[i], dpi[i+1], 1);
eat(dpi[i], dpd[i+1], 1);
}
if (inc[i] == -1) {
eat(dpd[i], dpi[i+1], -1);
eat(dpd[i], dpd[i+1], -1);
}
if (inc[i] == -1 && dec[i] == -1) {
eat(dpi[i], dpi[i+1], 0);
eat(dpd[i], dpd[i+1], 0);
}
else if (inc[i] == -1) {
eat(dpd[i], dpd[i+1], 0);
eat(dpi[i], dpi[dec[i]+1], 0);
}else if (dec[i] == -1) {
eat(dpi[i], dpi[i+1], 0);
eat(dpd[i], dpd[inc[i]+1], 0);
}else{
eat(dpi[i], dpi[dec[i]+1], 0);
eat(dpd[i], dpd[inc[i]+1], 0);
}
}
int re = 0;
REP(j,26) {
bug(j,dpi[0][j], dpd[0][j]);
ADD(re, dpi[0][j]);
ADD(re, dpd[0][j]);
}
cout<<re<<endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4172 KB |
Output is correct |
2 |
Correct |
2 ms |
4180 KB |
Output is correct |
3 |
Correct |
2 ms |
4180 KB |
Output is correct |
4 |
Correct |
2 ms |
4180 KB |
Output is correct |
5 |
Correct |
2 ms |
4180 KB |
Output is correct |
6 |
Correct |
2 ms |
4180 KB |
Output is correct |
7 |
Correct |
2 ms |
4176 KB |
Output is correct |
8 |
Correct |
2 ms |
4180 KB |
Output is correct |
9 |
Correct |
2 ms |
4180 KB |
Output is correct |
10 |
Correct |
2 ms |
4180 KB |
Output is correct |
11 |
Correct |
2 ms |
4180 KB |
Output is correct |
12 |
Correct |
2 ms |
4168 KB |
Output is correct |
13 |
Correct |
2 ms |
4168 KB |
Output is correct |
14 |
Correct |
3 ms |
4180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4172 KB |
Output is correct |
2 |
Correct |
2 ms |
4180 KB |
Output is correct |
3 |
Correct |
2 ms |
4180 KB |
Output is correct |
4 |
Correct |
2 ms |
4180 KB |
Output is correct |
5 |
Correct |
2 ms |
4180 KB |
Output is correct |
6 |
Correct |
2 ms |
4180 KB |
Output is correct |
7 |
Correct |
2 ms |
4176 KB |
Output is correct |
8 |
Correct |
2 ms |
4180 KB |
Output is correct |
9 |
Correct |
2 ms |
4180 KB |
Output is correct |
10 |
Correct |
2 ms |
4180 KB |
Output is correct |
11 |
Correct |
2 ms |
4180 KB |
Output is correct |
12 |
Correct |
2 ms |
4168 KB |
Output is correct |
13 |
Correct |
2 ms |
4168 KB |
Output is correct |
14 |
Correct |
3 ms |
4180 KB |
Output is correct |
15 |
Correct |
3 ms |
4180 KB |
Output is correct |
16 |
Correct |
3 ms |
4172 KB |
Output is correct |
17 |
Correct |
2 ms |
4300 KB |
Output is correct |
18 |
Correct |
2 ms |
4180 KB |
Output is correct |
19 |
Correct |
2 ms |
4180 KB |
Output is correct |
20 |
Correct |
2 ms |
4180 KB |
Output is correct |
21 |
Correct |
2 ms |
4196 KB |
Output is correct |
22 |
Correct |
5 ms |
4564 KB |
Output is correct |
23 |
Correct |
2 ms |
4180 KB |
Output is correct |
24 |
Correct |
2 ms |
4300 KB |
Output is correct |
25 |
Correct |
2 ms |
4180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4180 KB |
Output is correct |
2 |
Correct |
2 ms |
4180 KB |
Output is correct |
3 |
Correct |
2 ms |
4172 KB |
Output is correct |
4 |
Correct |
2 ms |
4168 KB |
Output is correct |
5 |
Correct |
279 ms |
124336 KB |
Output is correct |
6 |
Correct |
244 ms |
124408 KB |
Output is correct |
7 |
Correct |
271 ms |
120424 KB |
Output is correct |
8 |
Correct |
256 ms |
124328 KB |
Output is correct |
9 |
Correct |
260 ms |
120516 KB |
Output is correct |
10 |
Correct |
11 ms |
9076 KB |
Output is correct |
11 |
Correct |
2 ms |
4180 KB |
Output is correct |
12 |
Correct |
2 ms |
4180 KB |
Output is correct |
13 |
Correct |
268 ms |
124216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4172 KB |
Output is correct |
2 |
Correct |
2 ms |
4180 KB |
Output is correct |
3 |
Correct |
2 ms |
4180 KB |
Output is correct |
4 |
Correct |
2 ms |
4180 KB |
Output is correct |
5 |
Correct |
2 ms |
4180 KB |
Output is correct |
6 |
Correct |
2 ms |
4180 KB |
Output is correct |
7 |
Correct |
2 ms |
4176 KB |
Output is correct |
8 |
Correct |
2 ms |
4180 KB |
Output is correct |
9 |
Correct |
2 ms |
4180 KB |
Output is correct |
10 |
Correct |
2 ms |
4180 KB |
Output is correct |
11 |
Correct |
2 ms |
4180 KB |
Output is correct |
12 |
Correct |
2 ms |
4168 KB |
Output is correct |
13 |
Correct |
2 ms |
4168 KB |
Output is correct |
14 |
Correct |
3 ms |
4180 KB |
Output is correct |
15 |
Correct |
3 ms |
4180 KB |
Output is correct |
16 |
Correct |
3 ms |
4172 KB |
Output is correct |
17 |
Correct |
2 ms |
4300 KB |
Output is correct |
18 |
Correct |
2 ms |
4180 KB |
Output is correct |
19 |
Correct |
2 ms |
4180 KB |
Output is correct |
20 |
Correct |
2 ms |
4180 KB |
Output is correct |
21 |
Correct |
2 ms |
4196 KB |
Output is correct |
22 |
Correct |
5 ms |
4564 KB |
Output is correct |
23 |
Correct |
2 ms |
4180 KB |
Output is correct |
24 |
Correct |
2 ms |
4300 KB |
Output is correct |
25 |
Correct |
2 ms |
4180 KB |
Output is correct |
26 |
Correct |
10 ms |
9092 KB |
Output is correct |
27 |
Correct |
10 ms |
8632 KB |
Output is correct |
28 |
Correct |
10 ms |
8632 KB |
Output is correct |
29 |
Correct |
14 ms |
9020 KB |
Output is correct |
30 |
Correct |
12 ms |
9004 KB |
Output is correct |
31 |
Correct |
145 ms |
25188 KB |
Output is correct |
32 |
Correct |
17 ms |
8952 KB |
Output is correct |
33 |
Correct |
12 ms |
9096 KB |
Output is correct |
34 |
Correct |
13 ms |
9048 KB |
Output is correct |
35 |
Correct |
154 ms |
25248 KB |
Output is correct |
36 |
Correct |
9 ms |
8272 KB |
Output is correct |
37 |
Correct |
12 ms |
8788 KB |
Output is correct |
38 |
Correct |
11 ms |
8652 KB |
Output is correct |
39 |
Correct |
10 ms |
8540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4172 KB |
Output is correct |
2 |
Correct |
2 ms |
4180 KB |
Output is correct |
3 |
Correct |
2 ms |
4180 KB |
Output is correct |
4 |
Correct |
2 ms |
4180 KB |
Output is correct |
5 |
Correct |
2 ms |
4180 KB |
Output is correct |
6 |
Correct |
2 ms |
4180 KB |
Output is correct |
7 |
Correct |
2 ms |
4176 KB |
Output is correct |
8 |
Correct |
2 ms |
4180 KB |
Output is correct |
9 |
Correct |
2 ms |
4180 KB |
Output is correct |
10 |
Correct |
2 ms |
4180 KB |
Output is correct |
11 |
Correct |
2 ms |
4180 KB |
Output is correct |
12 |
Correct |
2 ms |
4168 KB |
Output is correct |
13 |
Correct |
2 ms |
4168 KB |
Output is correct |
14 |
Correct |
3 ms |
4180 KB |
Output is correct |
15 |
Correct |
3 ms |
4180 KB |
Output is correct |
16 |
Correct |
3 ms |
4172 KB |
Output is correct |
17 |
Correct |
2 ms |
4300 KB |
Output is correct |
18 |
Correct |
2 ms |
4180 KB |
Output is correct |
19 |
Correct |
2 ms |
4180 KB |
Output is correct |
20 |
Correct |
2 ms |
4180 KB |
Output is correct |
21 |
Correct |
2 ms |
4196 KB |
Output is correct |
22 |
Correct |
5 ms |
4564 KB |
Output is correct |
23 |
Correct |
2 ms |
4180 KB |
Output is correct |
24 |
Correct |
2 ms |
4300 KB |
Output is correct |
25 |
Correct |
2 ms |
4180 KB |
Output is correct |
26 |
Correct |
2 ms |
4180 KB |
Output is correct |
27 |
Correct |
2 ms |
4180 KB |
Output is correct |
28 |
Correct |
2 ms |
4172 KB |
Output is correct |
29 |
Correct |
2 ms |
4168 KB |
Output is correct |
30 |
Correct |
279 ms |
124336 KB |
Output is correct |
31 |
Correct |
244 ms |
124408 KB |
Output is correct |
32 |
Correct |
271 ms |
120424 KB |
Output is correct |
33 |
Correct |
256 ms |
124328 KB |
Output is correct |
34 |
Correct |
260 ms |
120516 KB |
Output is correct |
35 |
Correct |
11 ms |
9076 KB |
Output is correct |
36 |
Correct |
2 ms |
4180 KB |
Output is correct |
37 |
Correct |
2 ms |
4180 KB |
Output is correct |
38 |
Correct |
268 ms |
124216 KB |
Output is correct |
39 |
Correct |
10 ms |
9092 KB |
Output is correct |
40 |
Correct |
10 ms |
8632 KB |
Output is correct |
41 |
Correct |
10 ms |
8632 KB |
Output is correct |
42 |
Correct |
14 ms |
9020 KB |
Output is correct |
43 |
Correct |
12 ms |
9004 KB |
Output is correct |
44 |
Correct |
145 ms |
25188 KB |
Output is correct |
45 |
Correct |
17 ms |
8952 KB |
Output is correct |
46 |
Correct |
12 ms |
9096 KB |
Output is correct |
47 |
Correct |
13 ms |
9048 KB |
Output is correct |
48 |
Correct |
154 ms |
25248 KB |
Output is correct |
49 |
Correct |
9 ms |
8272 KB |
Output is correct |
50 |
Correct |
12 ms |
8788 KB |
Output is correct |
51 |
Correct |
11 ms |
8652 KB |
Output is correct |
52 |
Correct |
10 ms |
8540 KB |
Output is correct |
53 |
Correct |
217 ms |
113276 KB |
Output is correct |
54 |
Correct |
197 ms |
113324 KB |
Output is correct |
55 |
Correct |
244 ms |
124400 KB |
Output is correct |
56 |
Correct |
275 ms |
124328 KB |
Output is correct |
57 |
Correct |
263 ms |
124400 KB |
Output is correct |
58 |
Correct |
251 ms |
124428 KB |
Output is correct |
59 |
Correct |
275 ms |
124464 KB |
Output is correct |
60 |
Correct |
275 ms |
120536 KB |
Output is correct |
61 |
Correct |
180 ms |
105976 KB |
Output is correct |
62 |
Correct |
258 ms |
119760 KB |
Output is correct |
63 |
Correct |
215 ms |
113344 KB |
Output is correct |
64 |
Correct |
203 ms |
110480 KB |
Output is correct |