Submission #1175302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175302		KK_1729	Misspelling (JOI22_misspelling)	C++20	100 / 100	358 ms	187764 KiB

misspelling

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<int> a){
    for (auto x: a) cout << x << " ";

    cout << endl;
}
void solve(){
	int n, m; cin >> n >> m;
	vector<vector<int>> dp(n+1, vector<int>(26));

	vector<vector<int>> os(n+1);
	vector<vector<int>> og(n+1);
	FOR(i,0,m){
		int a, b; cin >> a >> b;
		if (a < b)og[a].pb(b);
		else if (a > b) os[b].pb(a);
	}

	FOR(i,0,26) dp[n][i] = 1;

	set<int> candid_g;
	set<int> candid_s;
	vector<int> sumg(26);
	vector<int> sums(26);
	for (int i = n-1; i >= 1; i--){
		candid_g.insert(i+1);
		candid_s.insert(i+1);

		FOR(j,0,26){
			sumg[j] += dp[i+1][j];
			sums[j] += dp[i+1][j];
		}

		for (auto x: og[i]){
			auto it = candid_g.lower_bound(i+1);
			while (it != candid_g.end() && (*it) <= x){
				FOR(j,0,26) sumg[j] -= dp[(*it)][j];
				it = candid_g.erase(it);
			}
		}

		for (auto x: os[i]){
			auto it = candid_s.lower_bound(i+1);
			while (it != candid_s.end() && (*it) <= x){
				FOR(j,0,26) sums[j] -= dp[(*it)][j];
				it = candid_s.erase(it);
			}
		}

		int u = 0;
		FOR(j,0,26){
			dp[i][j] += u;
			u += sums[j];
		}
		u = 0;
		for (int j = 25; j >= 0; j--){
			dp[i][j] += u;
			u += sumg[j];
		}
		FOR(j,0,26)dp[i][j]++;
		FOR(j,0,26) dp[i][j] %= 1000000007;
	}
	int ans = 0;
	FOR(j,0,26) ans += dp[1][j];
	ans %= 1000000007;
	cout << ans << endl;
}

int32_t main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int t = 1; // cin >> t;
    while (t--) solve();
}

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