Submission #632620

#	Time	Username	Problem	Language	Result	Execution time	Memory
632620		S2speed	Misspelling (JOI22_misspelling)	C++17	100 / 100	991 ms	269068 KiB

misspelling

#include<bits/stdc++.h>
 
using namespace std;
 
#pragma GCC optimize ("Ofast")
 
#define all(x) x.begin() , x.end()
typedef long long ll;
typedef pair<ll , ll> pll;
 
const ll maxn = 5e5 + 17 , md = 1e9 + 7 , inf = 2e16;
 
ll a[maxn][2];
vector<ll> b[maxn][2];
ll dp[maxn][26] , ps[maxn][26];
set<ll , greater<ll>> s[2];
 
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
	memset(a , -1 , sizeof(a));
	ll n , m;
	cin>>n>>m;
	for(ll i = 0 ; i < m ; i++){
		ll l , r;
		cin>>l>>r; l--; r--;
		bool f = false;
		if(l > r){
			swap(l , r); f = true;
		}
		a[l][f] = max(a[l][f] , r);
	}
	for(ll i = 0 ; i < n ; i++){
		if(a[i][0] != -1){
			b[a[i][0]][0].push_back(i);
		}
		if(a[i][1] != -1){
			b[a[i][1]][1].push_back(i);
		}
	}
	for(ll j = 0 ; j < 26 ; j++){
		ps[0][j] = dp[0][j] = 1;
	}
	s[0].insert(-1); s[1].insert(-1);
	for(ll i = 0 ; i < n - 1 ; i++){
		for(ll k = 0 ; k < 26 ; k++){
			dp[i][k] %= md;
		}
		if(i > 0){
			for(ll j = 0 ; j < 26 ; j++){
				ps[i][j] = ps[i - 1][j] + dp[i][j];
				ps[i][j] -= (ps[i][j] >= md) * md;
			}
		}
		if(a[i][0] != -1){
			s[0].insert(i);
		}
		if(a[i][1] != -1){
			s[1].insert(i);
		}
		for(ll c = 0 ; c < 2 ; c++){
			for(auto k : b[i][c]){
				s[c].erase(k);
			}
		}
		ll j[] = {*s[0].begin() , *s[1].begin()};
		for(ll k = 0 ; k < 26 ; k++){
			ll h = 0;
			h = ps[i][k] - (j[0] == -1 ? 0 : ps[j[0]][k]);
			h += (h < 0) * md;
			for(ll t = 0 ; t < k ; t++){
				dp[i + 1][t] += h;
			}
			h = ps[i][k] - (j[1] == -1 ? 0 : ps[j[1]][k]);
			h += (h < 0) * md;
			for(ll t = k + 1 ; t < 26 ; t++){
				dp[i + 1][t] += h;
			}
		}
	}
	ll ans = 0;
	for(ll i = 0 ; i < n ; i++){
		for(ll k = 0 ; k < 26 ; k++){
			ans += dp[i][k];
		}
		ans %= md;
	}
	ans %= md;
	cout<<ans<<'\n';
	return 0;
}

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