제출 #778843

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
778843		aZvezda	Misspelling (JOI22_misspelling)	C++14	100 / 100	1154 ms	245424 KiB

misspelling

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef LOCAL
#define cerr if(false)cerr
#endif

const ll mod = 1e9 + 7;

const ll MAX_N = 5e5 + 10;
const ll MAX_ALPH = 26;
ll dp[MAX_N][MAX_ALPH], pref[MAX_N][MAX_ALPH];
vector<pair<ll, ll> > starting[MAX_N];
ll n, m;

ll sum(ll l, ll r, ll ind) {
	if(r < l) { return 0; }
	if(l == 0) {
		return pref[r][ind];
	} else {
		return pref[r][ind] - pref[l - 1][ind];
	}
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	cin >> n >> m;
	for(ll i = 1; i <= m; i ++) {
		ll a, b;
		cin >> a >> b;
		if(a < b) {
			starting[a].push_back({b - 1, i});
		} else {
			starting[b].push_back({a - 1, -i});
		}
	}

	priority_queue<pair<ll, ll> > red, blue;
	for(ll i = 0; i < MAX_ALPH; i ++) {
		dp[0][i] = 1;
		pref[0][i] = 1;
	}
	for(ll i = 1; i < n; i ++) {
		for(const auto &it : starting[i]) {
			if(it.second < 0) {
				red.push({i, it.first});
			} else {
				blue.push({i, it.first});
			}
		}
		while(!red.empty() && red.top().second < i) { red.pop(); }
		while(!blue.empty() && blue.top().second < i) { blue.pop(); }

		ll last_red = red.empty() ? 0 : red.top().first;
		ll last_blue = blue.empty() ? 0 : blue.top().first;
		ll l = min(last_red, last_blue), r = max(last_red, last_blue);

		cerr << "Found diff " << last_red << " " << last_blue << endl;

		const auto fix = [&](auto &x) { x = (x % mod + mod) % mod; };

		for(ll j = 0; j < MAX_ALPH; j ++) {
			for(ll k = 0; k < j; k ++) {
				dp[i][k] += sum(r, i - 1, j);
				if(last_red > last_blue) {
					dp[i][k] += sum(l, r - 1, j);	
				}
				fix(dp[i][k]);
			}
			for(ll k = j + 1; k < MAX_ALPH; k ++) {
				dp[i][k] += sum(r, i - 1, j);
				if(last_red < last_blue) {
					dp[i][k] += sum(l, r - 1, j);	
				}
				fix(dp[i][k]);
			}
		}

		for(ll j = 0; j < MAX_ALPH; j ++) {
			cerr << dp[i][j] << " ";
			pref[i][j] = (pref[i - 1][j] + dp[i][j]) % mod;
		}
		cerr << endl;
	}
	ll ans = 0;
	for(ll i = 0; i < MAX_ALPH; i ++) {
		ans = (ans + pref[n - 1][i]) % mod;
	}
	cout << ans << endl;
}

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