제출 #544601

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
544601		sidon	Misspelling (JOI22_misspelling)	C++17	100 / 100	423 ms	146252 KiB

misspelling

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

const int Z = 5e5, B = 26, MOD = 1e9+7;

signed main() {
	ios::sync_with_stdio(0), cin.tie(0);

	int N, M;
	cin >> N >> M;

	vector<int> g[N], h[N];
	while(M--) {
		int u, v; cin >> u >> v;
		--u, --v;
		if(u < v) g[u].push_back(v);
		if(u > v) h[v].push_back(u);
	}

	int dp[N][B] {}, dpU[B] {}, dpD[B] {};
	vector<int> sU, sD;

	for(int i = N; i--; ) {
		for(int j : g[i]) {
			while(!empty(sU) && sU.back() <= j) {
				for(int k = B; k--; ) (dpU[k] -= dp[sU.back()][k]) %= MOD;
				sU.pop_back();
			}
		}
		for(int j : h[i]) {
			while(!empty(sD) && sD.back() <= j) {
				for(int k = B; k--; ) (dpD[k] -= dp[sD.back()][k]) %= MOD;
				sD.pop_back();
			}
		}
		fill(dp[i], dp[i] + B, 1);

		int sum = 0;
		for(int k = 0; k < B; ++k) {
			(dp[i][k] += sum) %= MOD;
			sum += dpD[k];
		}

		sum = 0;
		for(int k = B; k--; ) {
			(dp[i][k] += sum) %= MOD;
			sum += dpU[k];
		}

		for(int k = B; k--; ) {
			(dpU[k] += dp[i][k]) %= MOD;
			(dpD[k] += dp[i][k]) %= MOD;
		}
		sU.push_back(i);
		sD.push_back(i);
	}

	int ans = accumulate(dp[0], dp[0] + B, int(0)) % MOD;
	cout << (ans + MOD) % MOD;
}

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