Submission #936564

#	Time	Username	Problem	Language	Result	Execution time	Memory
936564		TAhmed33	Misspelling (JOI22_misspelling)	C++98	100 / 100	1118 ms	64316 KiB

misspelling

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int add (int a, int b) {
	a += b; if (a >= MOD) a -= MOD;
	return a;
}
int sub (int a, int b) {
	a -= b; if (a < 0) a += MOD;
	return a;
}
int mul (int a, int b) {
	return (a * 1ll * b) % MOD;
}
const int MAXN = 5e5 + 25;
int dp[MAXN][27];
int n, m, type1[MAXN], type2[MAXN];
int main () {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		int l = min(a, b), r = max(a, b);
		if (a > b) {
			type1[l] = max(type1[l], r);
		} else {
			type2[l] = max(type2[l], r);
		}
	}
	for (int i = 0; i < 26; i++) {
		dp[1][i] = 1;
	}
	vector <pair <int, int>> s1, s2;
	s1.push_back({1, type1[1]});
	s2.push_back({1, type2[1]});
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j < 26; j++) {
			int l = 0, r = (int)s2.size() - 1, ans = -1;
			while (l <= r) {
				int mid = (l + r) / 2;
				if (s2[mid].second >= i) {
					l = mid + 1; ans = mid;
				} else {
					r = mid - 1; 
				}
			}
			for (int k = 0; k < j; k++) {
				dp[i][j] = add(dp[i][j], sub(dp[i - 1][k], ans == -1 ? 0 : dp[s2[ans].first][k]));
			}
			l = 0, r = (int)s1.size() - 1, ans = -1;
			while (l <= r) {
				int mid = (l + r) / 2;
				if (s1[mid].second >= i) {
					l = mid + 1; ans = mid;
				} else {
					r = mid - 1; 
				}
			}
			for (int k = j + 1; k < 26; k++) {
				dp[i][j] = add(dp[i][j], sub(dp[i - 1][k], ans == -1 ? 0 : dp[s1[ans].first][k]));
			}
			dp[i][j] = add(dp[i][j], dp[i - 1][j]);
		}
		while (!s1.empty() && s1.back().second < type1[i]) s1.pop_back();
		s1.push_back({i, type1[i]});
		while (!s2.empty() && s2.back().second < type2[i]) s2.pop_back();
		s2.push_back({i, type2[i]});
	}
	int sum = 0;
	for (int i = 0; i < 26; i++) {
		sum = add(sum, dp[n][i]);
	}
	cout << sum << '\n';
}

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