oj.uz

Submission #422080

# Submission time Handle Problem Language Result Execution time Memory
422080 2021-06-09T17:13:07 Z valerikk Crossing (JOI21_crossing) C++17
26 / 100
 7000 ms 50304 KB 
#include <bits/stdc++.h>

using namespace std;

struct Query {
	int l, r, c;
};

int get_id(char c) {
	if (c == 'J') return 0;
	if (c == 'O') return 1;
	if (c == 'I') return 2;
	assert(0);
	return -1;
}

vector<int> read(int n) {
	string s;
	cin >> s;
	vector<int> res(n);
	for (int i = 0; i < n; ++i) res[i] = get_id(s[i]);
	return res;
}

int n, q;
vector<vector<int>> strs;
vector<int> t;
vector<Query> queries;
vector<vector<int>> pref;
set<pair<pair<int, int>, int>> st;
int cnt_good;

vector<int> vec_add(vector<int> a, vector<int> b) {
	vector<int> res(n);
	for (int i = 0; i < n; ++i) res[i] = (6 + -a[i] - b[i]) % 3;
	return res;
}

bool check(int l, int r, int c) {
	return pref[r][c] - pref[l][c] == r - l;
}

void insert(int l, int r, int c) {
	st.insert({{l, r}, c});
	if (check(l, r, c)) ++cnt_good;
}

void erase(int l, int r, int c) {
	st.erase({{l, r}, c});
	if (check(l, r, c)) --cnt_good;
}

int main() {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < 3; ++i) strs.push_back(read(n));

	{
		bool was = 1;
		while (was) {
			/*for (auto s : strs) {
				for (auto c : s) cout << c;
				cout << endl;
			}*/
			was = 0;
			vector<vector<int>> added;
			for (auto s1 : strs) {
				for (auto s2 : strs) {
					auto cur = vec_add(s1, s2);
					bool has = 0;
					for (auto s : strs) has |= cur == s;
					if (!has) {
						added.push_back(cur);
						was = 1;
					}
				}
			}
			for (auto s : added) strs.push_back(s);
		}
	}

	cin >> q;
	t = read(n);
	queries.resize(q);
	for (int i = 0; i < q; ++i) {
		cin >> queries[i].l >> queries[i].r;
		--queries[i].l;
		char c;
		cin >> c;
		queries[i].c = get_id(c);
	}
	vector<int> ans(q + 1, 0);

	for (auto s : strs) {
		pref.assign(n + 1, vector<int>(3, 0));
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < 3; ++j) pref[i + 1][j] = pref[i][j] + (s[i] == j);
		}
		st = {};
		cnt_good = 0;
		for (int i = 0; i < n; ++i) insert(i, i + 1, t[i]);
		for (int i = 0; i <= q; ++i) {
			ans[i] |= cnt_good == (int)st.size();
			if (i != q) {
				int l = queries[i].l, r = queries[i].r, c = queries[i].c;
				vector<pair<pair<int, int>, int>> inserted, erased;
				auto it = st.lower_bound({{l, -1}, -1});
				if (it != st.begin()) --it;
				for (int iteration = 0; it != st.end(); ++iteration, ++it) {
					int curl = it->first.first, curr = it->first.second, curc = it->second;
					if (curl >= r || curr <= l) {
						if (iteration == 0) {
							continue;
						} else {
							break;
						}
					}
					int cl = max(curl, l), cr = min(curr, r);
					erased.push_back({{curl, curr}, curc});
					inserted.push_back({{curl, cl}, curc});
					inserted.push_back({{cl, cr}, c});
					inserted.push_back({{cr, curr}, curc});
				}
				for (auto seg : erased) erase(seg.first.first, seg.first.second, seg.second);
				{
					vector<pair<pair<int, int>, int>> compressed;
					for (auto seg : inserted) {
						int curl = seg.first.first, curr = seg.first.second, curc = seg.second;
						if (curl >= curr) continue;
						if (compressed.empty() || curl > compressed.back().first.second || curc != compressed.back().second) {
							compressed.push_back({{curl, curr}, curc});
						} else {
							compressed.back().first.second = curr;
						}
					}
					inserted = compressed;
				}
				for (auto seg : inserted) insert(seg.first.first, seg.first.second, seg.second);
			}
		}
	}

	for (int i = 0; i <= q; ++i) cout << (ans[i] ? "Yes\n" : "No\n");
	return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 3752 KB Output is correct
2 Correct 504 ms 3980 KB Output is correct
3 Correct 410 ms 3968 KB Output is correct
4 Correct 540 ms 3924 KB Output is correct
5 Correct 585 ms 3864 KB Output is correct
6 Correct 531 ms 3812 KB Output is correct
7 Correct 527 ms 4036 KB Output is correct
8 Correct 563 ms 3984 KB Output is correct
9 Correct 589 ms 3956 KB Output is correct
10 Correct 620 ms 3984 KB Output is correct
11 Correct 563 ms 3976 KB Output is correct
12 Correct 629 ms 4036 KB Output is correct
13 Correct 567 ms 4036 KB Output is correct
14 Correct 564 ms 4036 KB Output is correct
15 Correct 562 ms 3988 KB Output is correct
16 Correct 573 ms 3980 KB Output is correct
17 Correct 570 ms 3980 KB Output is correct
18 Correct 376 ms 4080 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 3752 KB Output is correct
2 Correct 504 ms 3980 KB Output is correct
3 Correct 410 ms 3968 KB Output is correct
4 Correct 540 ms 3924 KB Output is correct
5 Correct 585 ms 3864 KB Output is correct
6 Correct 531 ms 3812 KB Output is correct
7 Correct 527 ms 4036 KB Output is correct
8 Correct 563 ms 3984 KB Output is correct
9 Correct 589 ms 3956 KB Output is correct
10 Correct 620 ms 3984 KB Output is correct
11 Correct 563 ms 3976 KB Output is correct
12 Correct 629 ms 4036 KB Output is correct
13 Correct 567 ms 4036 KB Output is correct
14 Correct 564 ms 4036 KB Output is correct
15 Correct 562 ms 3988 KB Output is correct
16 Correct 573 ms 3980 KB Output is correct
17 Correct 570 ms 3980 KB Output is correct
18 Correct 376 ms 4080 KB Output is correct
19 Correct 1081 ms 35604 KB Output is correct
20 Correct 934 ms 43084 KB Output is correct
21 Correct 1458 ms 48100 KB Output is correct
22 Correct 1306 ms 38484 KB Output is correct
23 Correct 808 ms 5904 KB Output is correct
24 Correct 799 ms 5824 KB Output is correct
25 Correct 1642 ms 50304 KB Output is correct
26 Correct 1408 ms 50296 KB Output is correct
27 Correct 1207 ms 50180 KB Output is correct
28 Correct 1260 ms 50132 KB Output is correct
29 Correct 1177 ms 49184 KB Output is correct
30 Correct 756 ms 5572 KB Output is correct
31 Correct 1180 ms 50200 KB Output is correct
32 Correct 1236 ms 47036 KB Output is correct
33 Correct 777 ms 5768 KB Output is correct
34 Correct 1233 ms 50172 KB Output is correct
35 Correct 1366 ms 35040 KB Output is correct
36 Correct 800 ms 5824 KB Output is correct
37 Correct 778 ms 5880 KB Output is correct
38 Correct 810 ms 49956 KB Output is correct
39 Correct 899 ms 31432 KB Output is correct
40 Correct 1385 ms 32120 KB Output is correct
41 Correct 596 ms 50248 KB Output is correct
42 Correct 568 ms 50196 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 3752 KB Output is correct
2 Correct 504 ms 3980 KB Output is correct
3 Correct 410 ms 3968 KB Output is correct
4 Correct 540 ms 3924 KB Output is correct
5 Correct 585 ms 3864 KB Output is correct
6 Correct 531 ms 3812 KB Output is correct
7 Correct 527 ms 4036 KB Output is correct
8 Correct 563 ms 3984 KB Output is correct
9 Correct 589 ms 3956 KB Output is correct
10 Correct 620 ms 3984 KB Output is correct
11 Correct 563 ms 3976 KB Output is correct
12 Correct 629 ms 4036 KB Output is correct
13 Correct 567 ms 4036 KB Output is correct
14 Correct 564 ms 4036 KB Output is correct
15 Correct 562 ms 3988 KB Output is correct
16 Correct 573 ms 3980 KB Output is correct
17 Correct 570 ms 3980 KB Output is correct
18 Correct 376 ms 4080 KB Output is correct
19 Correct 6648 ms 3856 KB Output is correct
20 Correct 5568 ms 3996 KB Output is correct
21 Correct 1275 ms 3980 KB Output is correct
22 Correct 1071 ms 3712 KB Output is correct
23 Correct 1279 ms 3976 KB Output is correct
24 Correct 1171 ms 3892 KB Output is correct
25 Correct 1304 ms 3976 KB Output is correct
26 Correct 1148 ms 3892 KB Output is correct
27 Correct 618 ms 4072 KB Output is correct
28 Correct 522 ms 3720 KB Output is correct
29 Correct 555 ms 4104 KB Output is correct
30 Correct 504 ms 3784 KB Output is correct
31 Execution timed out 7095 ms 3396 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 3752 KB Output is correct
2 Correct 504 ms 3980 KB Output is correct
3 Correct 410 ms 3968 KB Output is correct
4 Correct 540 ms 3924 KB Output is correct
5 Correct 585 ms 3864 KB Output is correct
6 Correct 531 ms 3812 KB Output is correct
7 Correct 527 ms 4036 KB Output is correct
8 Correct 563 ms 3984 KB Output is correct
9 Correct 589 ms 3956 KB Output is correct
10 Correct 620 ms 3984 KB Output is correct
11 Correct 563 ms 3976 KB Output is correct
12 Correct 629 ms 4036 KB Output is correct
13 Correct 567 ms 4036 KB Output is correct
14 Correct 564 ms 4036 KB Output is correct
15 Correct 562 ms 3988 KB Output is correct
16 Correct 573 ms 3980 KB Output is correct
17 Correct 570 ms 3980 KB Output is correct
18 Correct 376 ms 4080 KB Output is correct
19 Correct 1081 ms 35604 KB Output is correct
20 Correct 934 ms 43084 KB Output is correct
21 Correct 1458 ms 48100 KB Output is correct
22 Correct 1306 ms 38484 KB Output is correct
23 Correct 808 ms 5904 KB Output is correct
24 Correct 799 ms 5824 KB Output is correct
25 Correct 1642 ms 50304 KB Output is correct
26 Correct 1408 ms 50296 KB Output is correct
27 Correct 1207 ms 50180 KB Output is correct
28 Correct 1260 ms 50132 KB Output is correct
29 Correct 1177 ms 49184 KB Output is correct
30 Correct 756 ms 5572 KB Output is correct
31 Correct 1180 ms 50200 KB Output is correct
32 Correct 1236 ms 47036 KB Output is correct
33 Correct 777 ms 5768 KB Output is correct
34 Correct 1233 ms 50172 KB Output is correct
35 Correct 1366 ms 35040 KB Output is correct
36 Correct 800 ms 5824 KB Output is correct
37 Correct 778 ms 5880 KB Output is correct
38 Correct 810 ms 49956 KB Output is correct
39 Correct 899 ms 31432 KB Output is correct
40 Correct 1385 ms 32120 KB Output is correct
41 Correct 596 ms 50248 KB Output is correct
42 Correct 568 ms 50196 KB Output is correct
43 Correct 6648 ms 3856 KB Output is correct
44 Correct 5568 ms 3996 KB Output is correct
45 Correct 1275 ms 3980 KB Output is correct
46 Correct 1071 ms 3712 KB Output is correct
47 Correct 1279 ms 3976 KB Output is correct
48 Correct 1171 ms 3892 KB Output is correct
49 Correct 1304 ms 3976 KB Output is correct
50 Correct 1148 ms 3892 KB Output is correct
51 Correct 618 ms 4072 KB Output is correct
52 Correct 522 ms 3720 KB Output is correct
53 Correct 555 ms 4104 KB Output is correct
54 Correct 504 ms 3784 KB Output is correct
55 Execution timed out 7095 ms 3396 KB Time limit exceeded
56 Halted 0 ms 0 KB -