oj.uz

Submission #936560

# Submission time Handle Problem Language Result Execution time Memory
936560 2024-03-02T07:45:49 Z TAhmed33 Misspelling (JOI22_misspelling) C++
37 / 100
 894 ms 63828 KB 
#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 () {
  	ios::sync_with_stdio(0); cin.tie(0);
	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], 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], 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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 1 ms 2648 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 1 ms 2648 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Incorrect 1 ms 2396 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2504 KB Output is correct
5 Correct 721 ms 57484 KB Output is correct
6 Correct 712 ms 63824 KB Output is correct
7 Correct 725 ms 63716 KB Output is correct
8 Correct 710 ms 63828 KB Output is correct
9 Correct 734 ms 63788 KB Output is correct
10 Correct 28 ms 4432 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 894 ms 63716 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 1 ms 2648 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Incorrect 1 ms 2396 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 1 ms 2648 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Incorrect 1 ms 2396 KB Output isn't correct
18 Halted 0 ms 0 KB -