Submission #709213

#	Time	Username	Problem	Language	Result	Execution time	Memory
709213		minhcool	Misspelling (JOI22_misspelling)	C++17	100 / 100	1426 ms	277864 KiB

misspelling

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define fi first
#define se second
#define pb push_back
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 6e5 + 5;
const int mod = 1e9 + 7, oo = 1e18 + 7;
 
int n, q, a[N];
 
vector<iii> ques;
 
int dp[N][26];
 
int pref[N][26], suff[N][26];
 
set<ii> se[2];
 
int ck(int i, int j){// ck = 0 -> < , ck = 1 -> >; j < i
/*
	bool ck0 = 1, ck1 = 1;
	for(auto it : ques){
		if(it.fi.fi > j && it.fi.fi <= i && it.fi.se >= i){
			ck0 &= (it.se == 0);
			ck1 &= (it.se == 1);
		}
	}
	if(!ck0 && !ck1) return -1;
	else if(!ck1) return 0;
	else if(!ck0) return 1;
	else return 2;*/
	int temp0 = (se[0].size() ? (*se[0].rbegin()).fi : -oo), temp1 = (se[1].size() ? (*se[1].rbegin()).fi : -oo);
	bool ck0 = (temp1 <= j), ck1 = (temp0 <= j);
	if(!ck0 && !ck1) return -1;
	else if(!ck1) return 0;
	else if(!ck0) return 1;
	else return 2;
}
 
vector<ii> que[N];
 
void add(int &a, int b){
	a = (a + b) % mod;
}
 
int quee(int l, int r, int x){
//	cout << l << " " << r << " " << x << " " << pref[r][x] << " " << pref[l - 1][x] << "\n";
	if(l > r) return 0;
	else if(!l) return pref[r][x];
//	cout << l << " " << r << " " << x << " " << pref[r][x] << " " << pref[l - 1][x] << "\n";
	return (pref[r][x] - pref[l - 1][x] + mod) % mod;
}
 
void process(){
    cin >> n >> q;
    for(int i = 1; i <= q; i++){
    	int x, y;
    	cin >> x >> y;
    	if(x == y) continue;
    	if(x < y){
    		ques.pb({{x + 1, y}, 0});
    		que[x + 1].pb({i - 1, 0});
    		que[y].pb({i - 1, 1});	
		}
    	else{
    		ques.pb({{y + 1, x}, 1});
    		que[y + 1].pb({i - 1, 0});
    		que[x].pb({i - 1, 1});
		}
	}
	for(int i = 0; i < 26; i++) dp[1][i] = pref[1][i] = 1;
	for(int i = 2; i <= n; i++){
		for(auto it : que[i]){
			if(it.se == 0){
				se[ques[it.fi].se].insert({ques[it.fi].fi.fi, it.fi});
			}
		}
		int pos0 = (se[0].size() ? (*se[0].rbegin()).fi : -oo), pos1 = (se[1].size() ? (*se[1].rbegin()).fi : -oo);
		//cout << pos0 << " " << pos1 << "\n";
		/*
		for(int j = max(0LL, max(pos0, pos1)); j < i; j++){
			for(int k = 0; k < 26; k++){
				for(int h = 0; h < k; h++){
					add(dp[i][k], dp[j][h]);
				}
			}
			for(int k = 0; k < 26; k++){
				for(int h = k + 1; h < 26; h++){
					add(dp[i][k], dp[j][h]);		
				}
			}
		}*/
		int tol = 0;
		for(int k = 0; k < 26; k++){
			add(dp[i][k], tol);
			//cout << tol << "\n";
			add(tol, quee(max(0LL, max(pos0, pos1)), i - 1, k));
		}
		tol = 0;
		for(int k = 25; k >= 0; k--){
			add(dp[i][k], tol);
			add(tol, quee(max(0LL, max(pos0, pos1)), i - 1, k));
		}
		/*
		for(int j = max(0LL, min(pos0, pos1)); j < max(0LL, max(pos0, pos1)); j++){
			if(pos0 < pos1){
				for(int k = 0; k < 26; k++){
					for(int h = k + 1; h < 26; h++) add(dp[i][k], dp[j][h]);
				}
			}
			else{
				for(int k = 0; k < 26; k++){
					for(int h = 0; h < k; h++) add(dp[i][k], dp[j][h]);
				}
			}
		}*/
		if(pos0 < pos1){
			tol = 0;
			for(int k = 25; k >= 0; k--){
				add(dp[i][k], tol);
				//cout << tol << "\n";
				add(tol, quee(max(0LL, min(pos0, pos1)), max(0LL, max(pos0, pos1)) - 1, k));
			}
		}
		else{
			tol = 0;
			for(int k = 0; k < 26; k++){
				add(dp[i][k], tol);
				//cout << tol << "\n";
				add(tol, quee(max(0LL, min(pos0, pos1)), max(0LL, max(pos0, pos1)) - 1, k));
			}
		}
		/*
		for(int j = 1; j < i; j++){
			int temp = ck(i, j);
			//cout << i << " " << j << " " << temp << "\n";
			//cout << i << " " << j << " " << temp << "\n";
			if(temp == 0 || temp == 2){
				for(int k = 0; k < 26; k++){
					for(int h = 0; h < k; h++){
						add(dp[i][k], dp[j][h]);
					}
				}
			}
			if(temp == 1 || temp == 2){
				for(int k = 0; k < 26; k++){
					for(int h = k + 1; h < 26; h++){
						add(dp[i][k], dp[j][h]);		
					}
				}
			}
		}*/
		for(auto it : que[i]){
			if(it.se == 1){
				se[ques[it.fi].se].erase({ques[it.fi].fi.fi, it.fi});
			}
		}
		for(int j = 0; j < 26; j++){
		//	cout << i << " " << j << " " << dp[i][j] << "\n";
			pref[i][j] = pref[i - 1][j];
			add(pref[i][j], dp[i][j]);
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < 26; j++){
			add(ans, dp[i][j]);
		}
	}
	cout << ans << "\n";
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    //freopen("KEK.inp", "r", stdin);
    //freopen("KEK.out", "w", stdout);
    cin.tie(0);
    process();
}

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