Submission #905209

#	Time	Username	Problem	Language	Result	Execution time	Memory
905209		PM1	Misspelling (JOI22_misspelling)	C++17	100 / 100	389 ms	62512 KiB

misspelling

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define ll long long
const int mxn=5e5+5,M=1e9+7,Z=27;
int n,m,ps[mxn][Z],mx[2];
int mod(int x){
	return (x>=M)?x-M:x;
}
int sq(int x,int y,int xx,int yy){
	return mod(mod(mod(ps[x][y]-ps[xx][y]+M)-ps[x][yy]+M)+ps[xx][yy]);
}
priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int,int> > >pq[2];
priority_queue<pair<int,int>>s[2];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		if(x<y)
			pq[0].push({x,y});
		else
			pq[1].push({y,x});
	}
	for(int i=1;i<Z;i++)
		ps[1][i]=i;
	for(int i=2;i<=n;i++){
		for(int j=0;j<2;j++){
			while(pq[j].size() && pq[j].top().fr<i){
				s[j].push(pq[j].top());
				pq[j].pop();
			}
			while(s[j].size() && s[j].top().sc<i){
				s[j].pop();
			}
			mx[j]=(s[j].size())?s[j].top().fr:n+1;
		}
		//cout<<mx[0]<<" "<<mx[1]<<endl;
		for(int j=1;j<Z;j++){
			ps[i][j]=mod(mod(+ps[i-1][j]+ps[i][j-1])-ps[i-1][j-1]+M);
			if(mx[0]<mx[1]){
				if(mx[1]<i){
					ps[i][j]=mod(ps[i][j]+sq(i-1,26, mx[1],j));
					ps[i][j]=mod(ps[i][j]+sq(i-1,j-1,mx[1],0));
					if(mx[1]!=mx[0])ps[i][j]=mod(ps[i][j]+sq(mx[1],j-1,mx[0],0));
				}
				else if(mx[0]<i){
					ps[i][j]=mod(ps[i][j]+sq(i-1,26,0,j));
					ps[i][j]=mod(ps[i][j]+sq(i-1,j-1,mx[0],0));
				}
				else{
					ps[i][j]=mod(ps[i][j]+sq(i-1,26,0,j));
					ps[i][j]=mod(ps[i][j]+sq(i-1,j-1,0,0));
				}
			}
			else{
				if(mx[0]<i){
					ps[i][j]=mod(ps[i][j]+sq(i-1,26, mx[0],j));
					ps[i][j]=mod(ps[i][j]+sq(i-1,j-1,mx[0],0));
					if(mx[1]!=mx[0])ps[i][j]=mod(ps[i][j]+sq(mx[0],26,mx[1],j));
				}
				else if(mx[1]<i){
					ps[i][j]=mod(ps[i][j]+sq(i-1,26,mx[1],j));
					ps[i][j]=mod(ps[i][j]+sq(i-1,j-1,0,0));
				}
				else{
					ps[i][j]=mod(ps[i][j]+sq(i-1,26,0,j));
					ps[i][j]=mod(ps[i][j]+sq(i-1,j-1,0,0));
				}
			}
			//cout<<ps[i][j]<<" ";
		}//cout<<endl;
	}
	cout<<ps[n][Z-1]<<'\n';
}

• Subtask 1: 8 / 8
• Subtask 2: 20 / 20
• Subtask 3: 29 / 29
• Subtask 4: 32 / 32
• Subtask 5: 11 / 11