Submission #858792

#	Time	Username	Problem	Language	Result	Execution time	Memory
858792		willychan	Misspelling (JOI22_misspelling)	C++14	0 / 100	4045 ms	132312 KiB

misspelling

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds

const int MOD = 1000000007;
const int N = 5e5+5;
ll dp[N][26];
deque<int> belongs[4];
ll re[4][26];

void remove(int v,int k){
	for(int c=0;c<26;c++){
		re[k][c]-=dp[v][c];
		re[k][c]%=MOD;
	}
}
void add(int v,int k){
	//cout<<"adding "<<v<<" to "<<k<<":";
	for(int c=0;c<26;c++){
		re[k][c]+=dp[v][c];
		re[k][c]%=MOD;
		//cout<<re[k][c]<<" ";
	}
	//cout<<"\n";
}
vector<int> ran[N][2];
void printbelongs(){
	cout<<"--------------------\n";
	cout<<"printing...:\n";
	for(int k=0;k<4;k++){
		for(auto i : belongs[k]) cout<<i<<" ";
		cout<<"\n";
	}
	cout<<"--------------------\n";
}
void mantain(int r,bool t){
	if(t){
		stack<int> f10;
		stack<int> f11;
		while(belongs[0].size() && belongs[0][0]<=r){
			f10.push(belongs[0][0]);
			remove(belongs[0][0],0);
			belongs[0].pop_front();
		}
		while(belongs[1].size() && belongs[1][0]<=r){
			f11.push(belongs[1][0]);
			remove(belongs[1][0],1);
			belongs[1].pop_front();
		}
		while(f10.size()){
			belongs[2].push_front(f10.top());
			add(belongs[2][0],2);
			f10.pop();
		}
		while(f11.size()){
			belongs[3].push_front(f11.top());
			add(belongs[3][0],3);
			f11.pop();
		}
	}else{
		stack<int> f01;
		stack<int> f11;
		while(belongs[0].size() && belongs[0][0]<=r){
			f01.push(belongs[0][0]);
			remove(belongs[0][0],0);
			belongs[0].pop_front();
		}
		while(belongs[2].size() && belongs[2][0]<=r){
			f11.push(belongs[2][0]);
			remove(belongs[2][0],2);
			belongs[2].pop_front();
		}
		while(f01.size()){
			belongs[1].push_front(f01.top());
			add(belongs[1][0],1);
			f01.pop();
		}
		while(f11.size()){
			belongs[3].push_front(f11.top());
			add(belongs[3][0],3);
			f11.pop();
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,m;cin>>n>>m;	
	for(int i=0;i<m;i++){
		int a,b;cin>>a>>b;	
		bool w=  0;	
		if(a>b){w=1;swap(a,b);}
		ran[a+1][w].push_back(b);
	}
	for(int i=n;i>=1;i--){
		belongs[0].push_front(i);
		for(int c=0;c<26;c++){
			if(i==n) dp[i][c]=1;
			else{
				for(int f=0;f<26;f++){
					for(int k=0;k<4;k++){
						if(k==0 && f!=c) dp[i][c]+=re[k][f];
						if(k==1 && f>c) dp[i][c]+=re[k][f];
						if(k==2 && f<c) dp[i][c]+=re[k][f];
						dp[i][c]%=MOD;
					}
				}
				dp[i][c]++;
				dp[i][c]%=MOD;
			}
			//cout<<dp[i][c]<<" ";
		}
		//cout<<"\n";
		add(i,0);
		for(int b=0;b<2;b++){for(auto v : ran[i][b]) mantain(v,b);}
	
//		printbelongs();
	}
	ll ans = 0;
	for(int i=0;i<26;i++) ans=(ans+dp[1][i])%MOD;
	cout<<ans<<"\n";
	return 0;
}

// abba works...

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