Submission #546644

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
546644	2022-04-07T23:05:30 Z	inksamurai	Misspelling (JOI22_misspelling)	C++17	100 / 100	2332 ms	415804 KB

misspelling

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3x2WzQf ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e
 
 
//snuke's mod int
template <ll mod>
struct modint{
	ll x; // typedef long long ll;
	modint(ll x=0):x((x%mod+mod)%mod){}
	modint operator-()const{return modint(-x);}
	modint& operator+=(const modint a){if((x+=a.x)>=mod) x-=mod; return *this;}
	modint& operator-=(const modint a){if((x+=mod-a.x)>=mod) x-=mod; return *this;}
	modint& operator*=(const modint a){(x*=a.x)%=mod; return *this;}
	modint operator+(const modint a)const{modint res(*this); return res+=a;}
	modint operator-(const modint a)const{modint res(*this); return res-=a;}
	modint operator*(const modint a)const{modint res(*this); return res*=a;}
	modint pow(ll n)const{
		modint res=1,x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	modint inv()const{return pow(mod-2);}
};
 
using mint=modint<1000'000'007>;
 
mint dp[30][2],fdp[30][2];
 
signed main(){
_3x2WzQf;
	int n,m;
	cin>>n>>m;
 
	vec(vi) qry(n,vi(2,-1));
	rep(i,m){
		int l,r;
		cin>>l>>r;
		l-=1,r-=1;
		bool type=0;
		if(l>r){
			swap(l,r);
			type=1;
		}
		qry[l][type]=max(qry[l][type],r);
	}
 
	using tup=tuple<int,int,mint>;
	deque<tup> dq0,dq1;
 
	per(ch,26){
		dp[ch][0]=1;
	}
	per(i,n-1){
		int r0=qry[i][0];
		int r1=qry[i][1];
		rep(x,26){
			rep(y,26){
				if(x==y) continue;
				if(r0!=-1 and y>x) continue;
				if(r1!=-1 and y<x) continue;
				rep(t,2){
					int nt=(y>x?1:0);
					fdp[y][nt]+=dp[x][t];
				}
			}
		}
		rep(y,26){
			rep(nt,2){
				if(nt) dq1.pb({i,y,fdp[y][nt]});
				else dq0.pb({i,y,fdp[y][nt]});
				dp[y][nt]+=fdp[y][nt];
				fdp[y][nt]=0;
			}
		}
		while(sz(dq1)){
			auto &[j,ch,val]=dq1.back();
			if(j<r0){
				dp[ch][1]-=val;
				dq1.pop_back();
			}else{
				break;
			}
		}
		while(sz(dq0)){
			auto &[j,ch,val]=dq0.back();
			if(j<r1){
				dp[ch][0]-=val;
				dq0.pop_back();
			}else{
				break;
			}
		}
	}
 
	mint ans=0;
	rep(x,26){
		rep(t,2){
			ans+=dp[x][t];
		}
	}
 
	print(ans.x);
//	
	return 0;
}

Subtask #1
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct

Subtask #2
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	252 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	3 ms	212 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

Subtask #3
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1498 ms	27712 KB	Output is correct
6	Correct	1509 ms	27724 KB	Output is correct
7	Correct	1516 ms	27724 KB	Output is correct
8	Correct	1478 ms	27700 KB	Output is correct
9	Correct	1491 ms	27704 KB	Output is correct
10	Correct	60 ms	1424 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1621 ms	28988 KB	Output is correct

Subtask #4
32.0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	252 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	3 ms	212 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	60 ms	1364 KB	Output is correct
27	Correct	78 ms	9936 KB	Output is correct
28	Correct	80 ms	9948 KB	Output is correct
29	Correct	70 ms	2280 KB	Output is correct
30	Correct	71 ms	2260 KB	Output is correct
31	Correct	129 ms	2176 KB	Output is correct
32	Correct	61 ms	1428 KB	Output is correct
33	Correct	65 ms	1436 KB	Output is correct
34	Correct	74 ms	1592 KB	Output is correct
35	Correct	113 ms	1412 KB	Output is correct
36	Correct	97 ms	17632 KB	Output is correct
37	Correct	75 ms	1632 KB	Output is correct
38	Correct	80 ms	1492 KB	Output is correct
39	Correct	87 ms	1936 KB	Output is correct

Subtask #5
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	252 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	3 ms	212 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	0 ms	212 KB	Output is correct
27	Correct	0 ms	212 KB	Output is correct
28	Correct	0 ms	212 KB	Output is correct
29	Correct	0 ms	212 KB	Output is correct
30	Correct	1498 ms	27712 KB	Output is correct
31	Correct	1509 ms	27724 KB	Output is correct
32	Correct	1516 ms	27724 KB	Output is correct
33	Correct	1478 ms	27700 KB	Output is correct
34	Correct	1491 ms	27704 KB	Output is correct
35	Correct	60 ms	1424 KB	Output is correct
36	Correct	1 ms	212 KB	Output is correct
37	Correct	0 ms	212 KB	Output is correct
38	Correct	1621 ms	28988 KB	Output is correct
39	Correct	60 ms	1364 KB	Output is correct
40	Correct	78 ms	9936 KB	Output is correct
41	Correct	80 ms	9948 KB	Output is correct
42	Correct	70 ms	2280 KB	Output is correct
43	Correct	71 ms	2260 KB	Output is correct
44	Correct	129 ms	2176 KB	Output is correct
45	Correct	61 ms	1428 KB	Output is correct
46	Correct	65 ms	1436 KB	Output is correct
47	Correct	74 ms	1592 KB	Output is correct
48	Correct	113 ms	1412 KB	Output is correct
49	Correct	97 ms	17632 KB	Output is correct
50	Correct	75 ms	1632 KB	Output is correct
51	Correct	80 ms	1492 KB	Output is correct
52	Correct	87 ms	1936 KB	Output is correct
53	Correct	1946 ms	49204 KB	Output is correct
54	Correct	1913 ms	240740 KB	Output is correct
55	Correct	1678 ms	49028 KB	Output is correct
56	Correct	1689 ms	48940 KB	Output is correct
57	Correct	1509 ms	27716 KB	Output is correct
58	Correct	1507 ms	27716 KB	Output is correct
59	Correct	1500 ms	27732 KB	Output is correct
60	Correct	1831 ms	29004 KB	Output is correct
61	Correct	2332 ms	415804 KB	Output is correct
62	Correct	1912 ms	29112 KB	Output is correct
63	Correct	1995 ms	29244 KB	Output is correct
64	Correct	2159 ms	29560 KB	Output is correct

Submission #546644

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 20.0 / 20.0

Subtask #3 29.0 / 29.0

Subtask #4 32.0 / 32.0

Subtask #5 11.0 / 11.0

Subtask #1
8.0 / 8.0

Subtask #2
20.0 / 20.0

Subtask #3
29.0 / 29.0

Subtask #4
32.0 / 32.0

Subtask #5
11.0 / 11.0