Submission #591200

#	Time	Username	Problem	Language	Result	Execution time	Memory
591200		LastRonin	Misspelling (JOI22_misspelling)	C++14	100 / 100	776 ms	273096 KiB

misspelling

#pragma GCC optimize("O3")
 
#include <bits/stdc++.h> 
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define pill pair<ll, ll>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
 
const int N = 5e5 + 10;
const int M = 5e5 + 10;
const int C = 1e7 + 1e5;
const ll mod = 1e9 + 7;
const ll hsh[2] = {1555555699, 1222222763};
 
ll n, m, k;
ll a[M], b[M];
 
ll A[N], B[N];
 
ll sz = 0, ans = 0;
ll as[N];
ll pdp[N][26];
ll dp[26];
 
ll sprs[N][19];
ll sprs2[N][19];
      
 
ll maxA(ll l, ll r) {
    ll z = __lg(r - l + 1);
	return max(sprs[l][z], sprs[r - (1<<z) + 1][z]);	
}
 
ll maxB(ll l, ll r) {
    ll z = __lg(r - l + 1);
	return max(sprs2[l][z], sprs2[r - (1<<z) + 1][z]);	
}
 
void build() {
	for(int j = 1; j <= n; j++) {
		sprs[j][0] = A[j];
		sprs2[j][0] = B[j];
	}
	for(int i = 1; i < 19; i++) {
		for(int j = 1; j <= n - (1<<i) + 1; j++) {
			sprs[j][i] = max(sprs[j][i - 1], sprs[j + (1<<(i - 1))][i - 1]);
			sprs2[j][i] = max(sprs2[j][i - 1], sprs2[j + (1<<(i - 1))][i - 1]);	
		}
	}
}
 
int main() {
	speed;
	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		cin >> a[i] >> b[i];
		if(a[i] < b[i])
			A[a[i]] = max(b[i], A[a[i]]);
		else
			B[b[i]] = max(a[i], B[b[i]]);		
	}
	build();
	ll cnn = 0;
	for(int i = 1; i <= n; i++) {
		if(A[i])
			cnn++, a[cnn] = i, b[cnn] = A[i];
		if(B[i])
			cnn++, a[cnn] = B[i], b[cnn] = i;
	}
	m = cnn;
	for(int j = 0; j < 26; j++)
		pdp[1][j] = j + 1;
	for(int i = 2; i <= n; i++) {
		// <
		ll l = 1, r = i - 1, ans = i;
		while(l <= r) {
			ll m = (l + r) >> 1ll;
			if(maxA(m, i - 1) < i)
				r = m - 1, ans = m;	
			else
				l = m + 1;	
		}
		if(ans < i) {
			for(int k = 1; k < 26; k++) {
				dp[k] = (dp[k] + pdp[i - 1][k - 1] - pdp[ans - 1][k - 1] + mod) % mod;
			}
		}
		// >
		l = 1, r = i - 1, ans = i;
		while(l <= r) {
			ll m = (l + r) >> 1ll;
			if(maxB(m, i - 1) < i)
				r = m - 1, ans = m;	
			else
				l = m + 1;	
		}
		if(ans < i) {
			for(int k = 0; k < 26; k++) {
				dp[k] = (dp[k] + (pdp[i - 1][25] - pdp[ans - 1][25] - pdp[i - 1][k] + pdp[ans - 1][k]) + 3ll * mod) % mod;
			}
		}	
		for(int j = 0; j < 26; j++) {
			pdp[i][j] = (dp[j] + pdp[i - 1][j]) % mod;
			if(j < 25) dp[j + 1] = (dp[j + 1] + dp[j]) % mod;
			dp[j] = 0;
		}
	} 
	cout << pdp[n][25];
}

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