oj.uz

Submission #745069

# Submission time Handle Problem Language Result Execution time Memory
745069 2023-05-19T11:14:39 Z rt144 Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 35364 KB 
#include <bits/stdc++.h>
// #include <icecream.hpp>
using namespace std;
const int maxn = 3e5+5, inf = 2*maxn;
struct bst : set<pair<int, int>> {
	int prev = 0;
	int get_times(int x) {
		if (!empty() && rbegin()->second>=x) {
			return prev + x-rbegin()->first+1;
		} else return prev;
	}
	void toggle(int x) {
		if (empty() || rbegin()->second<x) {
			insert({x+1, inf});
		} else {
			int start = rbegin()->first;
			erase(--end()); insert({start, x});
			prev += x-start+1;
		}
	}
};
// using bst = set<pair<int, int>>;
int n, q;
bst st[maxn];

bst merge(bst &a, bst &b) {
	if (a.empty()) return a;
	if (b.empty()) return b;
	auto ai = a.begin(), bi = b.begin();
	bst nxt{};
	while (ai!=a.end() && bi!=b.end()) {
		auto [al, ar] = *ai; auto [bl, br] = *bi;
		if (al > br) bi++;
		else if (bl > ar) ai++;
		else {
			int l = max(al, bl), r = min(ar, br);
			nxt.insert({l, r});
			if (ar>br) bi++;
			else ai++;
		}
	}
	for (auto [l, r] : nxt) if (r!=inf) nxt.prev += r-l+1;
	return nxt;
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	cin >> n >> q; string init; cin >> init;
	for (int i=0;i<n;i++) if (init[i]=='1') st[i].toggle(0);
	// IC(st[0]);
	for (int i=1;i<=q;i++) {
		string res; cin >> res;
		if (res=="query") {
			int a, b; cin >> a >> b; //assert(b-a==1);
			bst res = st[a-1];
			for (int i=a;i<b-1;i++) {
				res = merge(res, st[i]);
			}
			cout << res.get_times(i) << '\n';
		} else {
			int a; cin >> a; st[a-1].toggle(i);
		}
		// IC(i, st[0]);
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 9 ms 16764 KB Output is correct
3 Correct 9 ms 16760 KB Output is correct
4 Correct 9 ms 16724 KB Output is correct
5 Correct 9 ms 16760 KB Output is correct
6 Correct 9 ms 16724 KB Output is correct
7 Correct 10 ms 16724 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2080 ms 21196 KB Output is correct
2 Correct 720 ms 21304 KB Output is correct
3 Correct 147 ms 21324 KB Output is correct
4 Correct 155 ms 28404 KB Output is correct
5 Correct 184 ms 32256 KB Output is correct
6 Correct 161 ms 29008 KB Output is correct
7 Correct 131 ms 17888 KB Output is correct
8 Correct 196 ms 33268 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 10 ms 16724 KB Output is correct
3 Correct 12 ms 16724 KB Output is correct
4 Correct 29 ms 16824 KB Output is correct
5 Correct 2445 ms 35364 KB Output is correct
6 Execution timed out 5062 ms 22940 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16724 KB Output is correct
2 Correct 13 ms 16808 KB Output is correct
3 Correct 10 ms 16812 KB Output is correct
4 Correct 9 ms 16724 KB Output is correct
5 Execution timed out 5079 ms 24788 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 9 ms 16764 KB Output is correct
3 Correct 9 ms 16760 KB Output is correct
4 Correct 9 ms 16724 KB Output is correct
5 Correct 9 ms 16760 KB Output is correct
6 Correct 9 ms 16724 KB Output is correct
7 Correct 10 ms 16724 KB Output is correct
8 Correct 2080 ms 21196 KB Output is correct
9 Correct 720 ms 21304 KB Output is correct
10 Correct 147 ms 21324 KB Output is correct
11 Correct 155 ms 28404 KB Output is correct
12 Correct 184 ms 32256 KB Output is correct
13 Correct 161 ms 29008 KB Output is correct
14 Correct 131 ms 17888 KB Output is correct
15 Correct 196 ms 33268 KB Output is correct
16 Correct 9 ms 16724 KB Output is correct
17 Correct 10 ms 16724 KB Output is correct
18 Correct 12 ms 16724 KB Output is correct
19 Correct 29 ms 16824 KB Output is correct
20 Correct 2445 ms 35364 KB Output is correct
21 Execution timed out 5062 ms 22940 KB Time limit exceeded
22 Halted 0 ms 0 KB -