Submission #551592

#	Time	Username	Problem	Language	Result	Execution time	Memory
551592		kshitij_sodani	Misspelling (JOI22_misspelling)	C++14	100 / 100	1093 ms	266512 KiB

misspelling

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
#define endl '\n'
const llo mod=1e9+7;
llo n,m;
vector<llo> pre3[500001];
llo dp[500001][26];
vector<pair<llo,llo>> pre2[500001];
llo pre[500001][26];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	for(llo i=0;i<m;i++){
		llo aa,bb;
		cin>>aa>>bb;
		aa--;
		bb--;
		llo cc=0;
		if(aa>bb){
			swap(aa,bb);
			cc=1;
		}
		//c=0 next is smaller
		pre3[aa].pb(cc);
		pre2[bb].pb({aa,cc});
	}
	multiset<llo> cur;
	multiset<llo> cur2;
	for(llo i=0;i<n;i++){
		if(i==0){
			for(llo j=0;j<26;j++){
				dp[i][j]=1;
			}
		}
		
		llo ma=0;
		llo ma2=0;
		if(cur.size()){
			auto j=cur.end();
			j--;
			ma=(*j)+1;
		}
		if(cur2.size()){
			auto j=cur2.end();
			j--;
			ma2=(*j)+1;
		}
		//cout<<i<<":"<<ma<<":"<<ma2<<endl;
		//max(ma,ma2) to i-1
		//min(ma,ma2) to max(ma,ma2)-1
		//rest is impossible
		pair<llo,llo> cur3={max(ma,ma2),i-1};
		if(cur3.a<=cur3.b){
			llo su=0;
			for(llo j=0;j<26;j++){
				su+=(pre[cur3.b+1][j]-pre[cur3.a][j]);
				if(su<0){
					su+=mod;
				}
				if(su>=mod){
					su-=mod;
				}
			}
			for(llo j=0;j<26;j++){
				dp[i][j]+=su;
				if(dp[i][j]>=mod){
					dp[i][j]-=mod;
				}
				llo cot=(pre[cur3.b+1][j]-pre[cur3.a][j]);
				if(cot<0){
					cot+=mod;
				}
				dp[i][j]-=cot;
				if(dp[i][j]<0){
					dp[i][j]+=mod;
				}
				if(dp[i][j]>=mod){
					dp[i][j]-=mod;
				}
			}

		}
	/*	for(llo k=max(ma,ma2);k<=i-1;k++){
			llo su=0;
			for(llo j=0;j<26;j++){
				su+=dp[k][j];
				if(su>=mod){
					su-=mod;
				}
			}
			for(llo j=0;j<26;j++){
				dp[i][j]+=(su-dp[k][j]+mod);
				if(dp[i][j]>=mod){
					dp[i][j]-=mod;
				}
				if(dp[i][j]>=mod){
					dp[i][j]-=mod;
				}
			}
		}*/
		cur3={min(ma,ma2),max(ma,ma2)-1};
		if(cur3.a<=cur3.b){
			if(ma<ma2){
				//no restrictions x>y
				llo su=0;
				for(llo j=25;j>=0;j--){
					dp[i][j]+=su;
					if(dp[i][j]>=mod){
						dp[i][j]-=mod;
					}
					//cout<<cur3.a<<",,"<<cur3.b+1<<endl;
					llo cot=pre[cur3.b+1][j]-pre[cur3.a][j]+mod;
					if(cot>=mod){
						cot-=mod;
					}
					
					su+=cot;
					if(su>=mod){
						su-=mod;
					}
				}
			}
			else{

				//x>y always
				llo su=0;
				for(llo j=0;j<26;j++){
					dp[i][j]+=su;
					if(dp[i][j]>=mod){
						dp[i][j]-=mod;
					}
					llo cot=pre[cur3.b+1][j]-pre[cur3.a][j];
					if(cot<0){
						cot+=mod;
					}
					su+=cot;
					if(su>=mod){
						su-=mod;
					}
				}
			}




		}
	/*	for(llo k=min(ma,ma2);k<=max(ma,ma2)-1;k++){
			if(ma<ma2){
				//no restrictions x>y
				llo su=0;
				for(llo j=25;j>=0;j--){
					dp[i][j]+=su;
					if(dp[i][j]>=mod){
						dp[i][j]-=mod;
					}
					su+=dp[k][j];
					if(su>=mod){
						su-=mod;
					}
				}
			}
			else{

				//x>y always
				llo su=0;
				for(llo j=0;j<26;j++){
					dp[i][j]+=su;
					if(dp[i][j]>=mod){
						dp[i][j]-=mod;
					}
					su+=dp[k][j];
					if(su>=mod){
						su-=mod;
					}
				}
			}
		}*/
	/*	if(ma<ma2){

		}
		else if(ma>ma2){

		}
*/





		for(auto j:pre3[i]){
			if(j==0){
				cur.insert(i);
			}
			else{
				cur2.insert(i);
			}
		}
		for(auto j:pre2[i]){
			if(j.b==1){
				auto jj=cur2.find(j.a);
				cur2.erase(jj);
			}
			else{
				auto jj=cur.find(j.a);
				cur.erase(jj);
			}
		}
		for(int j=0;j<26;j++){
			pre[i+1][j]=pre[i][j]+dp[i][j];
			if(pre[i+1][j]>=mod){
				pre[i+1][j]-=mod;
			}
		}
	}

	llo ans=0;
	for(llo i=0;i<n;i++){
		for(llo j=0;j<26;j++){
			//cout<<i<<":"<<j<<":"<<dp[i][j]<<endl;
			ans=(ans+dp[i][j]);
			if(ans>=mod){
				ans-=mod;
			}
		}	
	}
	cout<<ans<<endl;







	return 0;
}

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