oj.uz

Submission #745059

# Submission time Handle Problem Language Result Execution time Memory
745059 2023-05-19T10:54:27 Z rt144 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 172 ms 38984 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];

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);
			cout << st[a-1].get_times(i) << '\n';
		} else {
			int a; cin >> a; st[a-1].toggle(i);
		}
		// IC(i, st[0]);
	}
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 33748 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 21180 KB Output is correct
2 Correct 99 ms 24652 KB Output is correct
3 Correct 100 ms 25328 KB Output is correct
4 Correct 171 ms 33356 KB Output is correct
5 Correct 153 ms 37340 KB Output is correct
6 Correct 158 ms 33840 KB Output is correct
7 Correct 122 ms 23692 KB Output is correct
8 Correct 172 ms 38984 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 33832 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 33828 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 33748 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -