oj.uz

Submission #727118

# Submission time Handle Problem Language Result Execution time Memory
727118 2023-04-20T04:38:39 Z SanguineChameleon Street Lamps (APIO19_street_lamps) C++17
60 / 100
 5000 ms 130904 KB 
#include <bits/stdc++.h>
using namespace std;

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

struct node {
	int pref, suf;
	vector<pair<int, int>> left_events;
	vector<pair<int, int>> right_events;
	vector<pair<int, pair<int, int>>> queries;
};

const int maxN = 3e5 + 20;
int a[maxN];
int res[maxN];
node tr[maxN * 4];
int sum_single[maxN];
int prv_single[maxN];

void add_event(int id, int T) {
	if (tr[id].left_events.empty() || tr[id * 2].suf != tr[id].left_events.back().second) {
		tr[id].left_events.push_back({T, tr[id * 2].suf});
	}
	if (tr[id].right_events.empty() || tr[id * 2 + 1].pref != tr[id].right_events.back().second) {
		tr[id].right_events.push_back({T, tr[id * 2 + 1].pref});
	}
}

void merge(int id, int lt, int rt, int mt, int T) {
	tr[id].pref = tr[id * 2].pref + (tr[id * 2].pref == mt - lt + 1 ? tr[id * 2 + 1].pref : 0);
	tr[id].suf = tr[id * 2 + 1].suf + (tr[id * 2 + 1].suf == rt - mt ? tr[id * 2].suf : 0);
	add_event(id, T);
}

void build(int id, int lt, int rt) {
	if (lt == rt) {
		tr[id].pref = a[lt];
		tr[id].suf = a[lt];
		return;
	}
	int mt = (lt + rt) / 2;
	build(id * 2, lt, mt);
	build(id * 2 + 1, mt + 1, rt);
	merge(id, lt, rt, mt, 0);
}

void update(int id, int lt, int rt, int pos, int T) {
	if (lt == rt) {
		if (a[lt] == 1) {
			sum_single[lt] += T - prv_single[lt];
		}
		prv_single[lt] = T;
		a[lt] ^= 1;
		tr[id].pref = a[lt];
		tr[id].suf = a[lt];
		return;
	}
	int mt = (lt + rt) / 2;
	if (pos <= mt) {
		update(id * 2, lt, mt, pos, T);
	}
	else {
		update(id * 2 + 1, mt + 1, rt, pos, T);
	}
	merge(id, lt, rt, mt, T);
}

void add(int id, int lt, int rt, int ql, int qr, int T) {
	if (lt == rt) {
		res[T] = sum_single[lt];
		if (a[lt] == 1) {
			res[T] += T - prv_single[lt];
		}
		return;
	}
	int mt = (lt + rt) / 2;
	if (qr <= mt) {
		add(id * 2, lt, mt, ql, qr, T);
	}
	else if (ql >= mt + 1) {
		add(id * 2 + 1, mt + 1, rt, ql, qr, T);
	}
	else {
		tr[id].queries.push_back({T, {mt - ql + 1, qr - mt}});
	}
}

void solve(int id) {
	vector<pair<int, pair<int, int>>> &queries = tr[id].queries;
	vector<pair<int, int>> &left_events = tr[id].left_events;
	vector<pair<int, int>> &right_events = tr[id].right_events;
	if (queries.empty()) {
		return;
	}
	int sz_left = left_events.size();
	int sz_right = right_events.size();
	for (auto q: queries) {
		int T = q.first;
		int X = q.second.first;
		int Y = q.second.second;
		res[T] = 0;
		for (int i = 0; i < sz_left; i++) {
			if (left_events[i].second >= X) {
				for (int j = 0; j < sz_right; j++) {
					if (right_events[j].second >= Y) {
						int lt = 0;
						int rt = T - 1;
						lt = max(lt, left_events[i].first);
						if (i + 1 < sz_left) {
							rt = min(rt, left_events[i + 1].first - 1);
						}
						lt = max(lt, right_events[j].first);
						if (j + 1 < sz_right) {
							rt = min(rt, right_events[j + 1].first - 1);
						}
						if (lt <= rt) {
							res[T] += rt - lt + 1;
						}
					}
				}
			}
		}
	}
}

void solve(int id, int lt, int rt) {
	if (lt == rt) {
		return;
	}
	solve(id);
	int mt = (lt + rt) / 2;
	solve(id * 2, lt, mt);
	solve(id * 2 + 1, mt + 1, rt);
}

void just_do_it() {
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		char c;
		cin >> c;
		a[i] = c - '0';
	}
	build(1, 1, n);
	for (int T = 1; T <= q; T++) {
		res[T] = -1;
		string s;
		cin >> s;
		if (s == "toggle") {
			int pos;
			cin >> pos;
			update(1, 1, n, pos, T);
		}
		if (s == "query") {
			int ql, qr;
			cin >> ql >> qr;
			qr--;
			add(1, 1, n, ql, qr, T);
		}
	}
	solve(1, 1, n);
	for (int i = 1; i <= q; i++) {
		if (res[i] != -1) {
			cout << res[i] << '\n';
		}
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94156 KB Output is correct
2 Correct 45 ms 94200 KB Output is correct
3 Correct 50 ms 94228 KB Output is correct
4 Correct 44 ms 94156 KB Output is correct
5 Correct 43 ms 94296 KB Output is correct
6 Correct 42 ms 94184 KB Output is correct
7 Correct 43 ms 94152 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 101324 KB Output is correct
2 Correct 146 ms 100988 KB Output is correct
3 Correct 180 ms 101660 KB Output is correct
4 Correct 404 ms 122280 KB Output is correct
5 Correct 443 ms 121532 KB Output is correct
6 Correct 421 ms 123464 KB Output is correct
7 Correct 223 ms 116044 KB Output is correct
8 Correct 225 ms 117508 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94408 KB Output is correct
2 Correct 44 ms 94264 KB Output is correct
3 Correct 43 ms 94380 KB Output is correct
4 Correct 43 ms 94264 KB Output is correct
5 Correct 632 ms 128908 KB Output is correct
6 Correct 532 ms 128728 KB Output is correct
7 Correct 410 ms 128384 KB Output is correct
8 Correct 235 ms 127856 KB Output is correct
9 Correct 117 ms 101940 KB Output is correct
10 Correct 133 ms 103752 KB Output is correct
11 Correct 128 ms 102932 KB Output is correct
12 Correct 224 ms 126500 KB Output is correct
13 Correct 232 ms 127784 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 94288 KB Output is correct
2 Correct 46 ms 94344 KB Output is correct
3 Correct 45 ms 94272 KB Output is correct
4 Correct 48 ms 94336 KB Output is correct
5 Correct 226 ms 129052 KB Output is correct
6 Correct 352 ms 128340 KB Output is correct
7 Correct 449 ms 129372 KB Output is correct
8 Correct 575 ms 130904 KB Output is correct
9 Correct 4446 ms 107792 KB Output is correct
10 Execution timed out 5024 ms 107468 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94156 KB Output is correct
2 Correct 45 ms 94200 KB Output is correct
3 Correct 50 ms 94228 KB Output is correct
4 Correct 44 ms 94156 KB Output is correct
5 Correct 43 ms 94296 KB Output is correct
6 Correct 42 ms 94184 KB Output is correct
7 Correct 43 ms 94152 KB Output is correct
8 Correct 134 ms 101324 KB Output is correct
9 Correct 146 ms 100988 KB Output is correct
10 Correct 180 ms 101660 KB Output is correct
11 Correct 404 ms 122280 KB Output is correct
12 Correct 443 ms 121532 KB Output is correct
13 Correct 421 ms 123464 KB Output is correct
14 Correct 223 ms 116044 KB Output is correct
15 Correct 225 ms 117508 KB Output is correct
16 Correct 41 ms 94408 KB Output is correct
17 Correct 44 ms 94264 KB Output is correct
18 Correct 43 ms 94380 KB Output is correct
19 Correct 43 ms 94264 KB Output is correct
20 Correct 632 ms 128908 KB Output is correct
21 Correct 532 ms 128728 KB Output is correct
22 Correct 410 ms 128384 KB Output is correct
23 Correct 235 ms 127856 KB Output is correct
24 Correct 117 ms 101940 KB Output is correct
25 Correct 133 ms 103752 KB Output is correct
26 Correct 128 ms 102932 KB Output is correct
27 Correct 224 ms 126500 KB Output is correct
28 Correct 232 ms 127784 KB Output is correct
29 Correct 51 ms 94288 KB Output is correct
30 Correct 46 ms 94344 KB Output is correct
31 Correct 45 ms 94272 KB Output is correct
32 Correct 48 ms 94336 KB Output is correct
33 Correct 226 ms 129052 KB Output is correct
34 Correct 352 ms 128340 KB Output is correct
35 Correct 449 ms 129372 KB Output is correct
36 Correct 575 ms 130904 KB Output is correct
37 Correct 4446 ms 107792 KB Output is correct
38 Execution timed out 5024 ms 107468 KB Time limit exceeded
39 Halted 0 ms 0 KB -