#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rrep(i,l,r) for(int i=l;i<=r;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#define unq(x) sort(all(x));x.erase(unique(all(x)),x.end())
#define mod 1000000007
#define ad(a,b) a=(a+b)%mod;
#define mul(a,b) a=a*b%mod;
#define N 500010
#define M 500010
#define K 26
class STACK{
private:
stack<pll> s;
public:
ll sum;
void init(){
sum=0;
}
void add(ll pos,ll val){
s.push(mp(pos,val));
ad(sum,val);
}
void ers(ll ul){//erase[-inf,ul]
while(!s.empty()){
if(s.top().first>ul)break;
ad(sum,-s.top().second);
s.pop();
}
}
};
STACK stc[26][2];
ll n,m;
ll a[M],b[M];
ll maxb[N][2];
int main(){
cin.tie(0);
ios::sync_with_stdio(0);
cin>>n>>m;
rep(i,n){
rep(f,2){
maxb[i][f]=-1e18;
}
}
rep(i,m){
cin>>a[i]>>b[i];
a[i]--,b[i]--;
ll x=min(a[i],b[i]);
ll y=max(a[i],b[i]);
chmax(maxb[x][a[i]<b[i]],y);
}
rep(c,26)rep(f,2)stc[c][f].init();
rep(c,26){
stc[c][0].add(n,1);
}
for(int pos=n-1;pos>0;pos--){
ll sums[26][2];
rep(c,26)rep(ud,2)sums[c][ud]=stc[c][ud].sum;
rep(c,26)rep(ud,2){
stc[c][ud].ers(maxb[pos-1][ud^1]);
}
if(pos>maxb[pos-1][0]){
ll rui=0;
rep(c,26){
stc[c][1].add(pos,rui);
rep(ud,2){
ad(rui,sums[c][ud]);
}
}
}
if(pos>maxb[pos-1][1]){
ll rui=0;
per(c,26){
stc[c][0].add(pos,rui);
rep(ud,2){
ad(rui,sums[c][ud]);
}
}
}
}
ll ans=0;
rep(c,26)rep(ud,2){
ad(ans,stc[c][ud].sum);
}
if(ans<0)ans+=mod;
cout<<ans<<endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
368 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
368 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
2 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
368 KB |
Output is correct |
19 |
Correct |
1 ms |
368 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
2 ms |
340 KB |
Output is correct |
22 |
Correct |
4 ms |
544 KB |
Output is correct |
23 |
Correct |
1 ms |
468 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
356 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
368 KB |
Output is correct |
5 |
Correct |
359 ms |
22584 KB |
Output is correct |
6 |
Correct |
412 ms |
22604 KB |
Output is correct |
7 |
Correct |
421 ms |
22288 KB |
Output is correct |
8 |
Correct |
388 ms |
22236 KB |
Output is correct |
9 |
Correct |
392 ms |
22556 KB |
Output is correct |
10 |
Correct |
20 ms |
1220 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
441 ms |
23832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
368 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
2 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
368 KB |
Output is correct |
19 |
Correct |
1 ms |
368 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
2 ms |
340 KB |
Output is correct |
22 |
Correct |
4 ms |
544 KB |
Output is correct |
23 |
Correct |
1 ms |
468 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
21 ms |
1040 KB |
Output is correct |
27 |
Correct |
23 ms |
9592 KB |
Output is correct |
28 |
Correct |
29 ms |
9536 KB |
Output is correct |
29 |
Correct |
17 ms |
1876 KB |
Output is correct |
30 |
Correct |
17 ms |
2088 KB |
Output is correct |
31 |
Correct |
104 ms |
13976 KB |
Output is correct |
32 |
Correct |
16 ms |
1056 KB |
Output is correct |
33 |
Correct |
18 ms |
1108 KB |
Output is correct |
34 |
Correct |
20 ms |
1364 KB |
Output is correct |
35 |
Correct |
101 ms |
12280 KB |
Output is correct |
36 |
Correct |
34 ms |
17228 KB |
Output is correct |
37 |
Correct |
20 ms |
1260 KB |
Output is correct |
38 |
Correct |
20 ms |
1136 KB |
Output is correct |
39 |
Correct |
21 ms |
1276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
368 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
2 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
368 KB |
Output is correct |
19 |
Correct |
1 ms |
368 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
2 ms |
340 KB |
Output is correct |
22 |
Correct |
4 ms |
544 KB |
Output is correct |
23 |
Correct |
1 ms |
468 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
356 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
368 KB |
Output is correct |
30 |
Correct |
359 ms |
22584 KB |
Output is correct |
31 |
Correct |
412 ms |
22604 KB |
Output is correct |
32 |
Correct |
421 ms |
22288 KB |
Output is correct |
33 |
Correct |
388 ms |
22236 KB |
Output is correct |
34 |
Correct |
392 ms |
22556 KB |
Output is correct |
35 |
Correct |
20 ms |
1220 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
340 KB |
Output is correct |
38 |
Correct |
441 ms |
23832 KB |
Output is correct |
39 |
Correct |
21 ms |
1040 KB |
Output is correct |
40 |
Correct |
23 ms |
9592 KB |
Output is correct |
41 |
Correct |
29 ms |
9536 KB |
Output is correct |
42 |
Correct |
17 ms |
1876 KB |
Output is correct |
43 |
Correct |
17 ms |
2088 KB |
Output is correct |
44 |
Correct |
104 ms |
13976 KB |
Output is correct |
45 |
Correct |
16 ms |
1056 KB |
Output is correct |
46 |
Correct |
18 ms |
1108 KB |
Output is correct |
47 |
Correct |
20 ms |
1364 KB |
Output is correct |
48 |
Correct |
101 ms |
12280 KB |
Output is correct |
49 |
Correct |
34 ms |
17228 KB |
Output is correct |
50 |
Correct |
20 ms |
1260 KB |
Output is correct |
51 |
Correct |
20 ms |
1136 KB |
Output is correct |
52 |
Correct |
21 ms |
1276 KB |
Output is correct |
53 |
Correct |
574 ms |
37100 KB |
Output is correct |
54 |
Correct |
607 ms |
229076 KB |
Output is correct |
55 |
Correct |
505 ms |
37456 KB |
Output is correct |
56 |
Correct |
488 ms |
44116 KB |
Output is correct |
57 |
Correct |
398 ms |
22596 KB |
Output is correct |
58 |
Correct |
373 ms |
19016 KB |
Output is correct |
59 |
Correct |
374 ms |
15996 KB |
Output is correct |
60 |
Correct |
507 ms |
17312 KB |
Output is correct |
61 |
Correct |
789 ms |
397488 KB |
Output is correct |
62 |
Correct |
576 ms |
20440 KB |
Output is correct |
63 |
Correct |
539 ms |
17088 KB |
Output is correct |
64 |
Correct |
537 ms |
13556 KB |
Output is correct |