oj.uz

Submission #949884

# Submission time Handle Problem Language Result Execution time Memory
949884 2024-03-19T20:04:47 Z MinaRagy06 Street Lamps (APIO19_street_lamps) C++17
100 / 100
 1072 ms 49448 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 300'005;
struct BIT {
	int n, bit[N];
	void init(int _n) {
		n = _n;
		for (int i = 0; i < n; i++) {
			bit[i] = 0;
		}
	}
	int get(int r) {
		int ans = 0;
		for (int i = r; i >= 0; i = (i & (i + 1)) - 1) {
			ans += bit[i];
		}
		return ans;
	}
	void add(int x, int v) {
		for (int i = x; i < n; i = i | (i + 1)) {
			bit[i] += v;
		}
	}
} bit;
int ans[N];
vector<array<int, 2>> upd[N], ask[N];
void process(vector<array<int, 3>> &add, vector<array<int, 3>> &q) {
	vector<int> gud;
	for (auto [l, r, v] : add) {
		gud.push_back(l);
		gud.push_back(r);
	}
	for (auto [l, r, idx] : q) {
		gud.push_back(l);
		gud.push_back(r);
	}
	sort(gud.begin(), gud.end());
	gud.resize(unique(gud.begin(), gud.end()) - gud.begin());
	auto get = [&] (int x) {
		return (int) (lower_bound(gud.begin(), gud.end(), x) - gud.begin());
	};
	int n = gud.size();
	for (int i = 0; i < n; i++) {
		upd[i].clear();
		ask[i].clear();
	}
	bit.init(n);
	for (auto [l, r, v] : add) {
		upd[get(l)].push_back({get(r), v});
	}
	for (auto [l, r, idx] : q) {
		ask[get(l)].push_back({get(r), idx});
	}
	for (int l = 0; l < n; l++) {
		for (auto [r, v] : upd[l]) {
			bit.add(n - 1 - r, v);
		}
		for (auto [r, idx] : ask[l]) {
			ans[idx] += bit.get(n - 1 - r);
		}
	}
}
void solve(int l, int r, vector<array<int, 4>> &qq) {
	if (l >= r) return;
	int md = (l + r) / 2;
	vector<array<int, 3>> v1, v2;
	for (int i = l; i <= md; i++) {
		if (qq[i][0] == 1) {
			v1.push_back({qq[i][1], qq[i][2], qq[i][3]});
		}
	}
	for (int i = md + 1; i <= r; i++) {
		if (qq[i][0] == 0) {
			v2.push_back({qq[i][1], qq[i][2], qq[i][3]});
		}
	}
	process(v1, v2);
	solve(l, md, qq);
	solve(md + 1, r, qq);
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n, q;
	cin >> n >> q;
	string arr;
	cin >> arr;
	arr += '0';
	int lst = -1;
	set<array<int, 3>> s;
	vector<array<int, 4>> qq;
	for (int i = 0; i <= n; i++) {
		if (arr[i] == '1') continue;
		if (lst + 1 <= i - 1) {
			s.insert({lst + 1, i - 1, 0});
		}
		lst = i;
	}
	for (int k = 1; k <= q; k++) {
		string type;
		cin >> type;
		if (type == "toggle") {
			ans[k] = -1;
			int i;
			cin >> i;
			i--;
			if (arr[i] == '1') {
				auto it = s.lower_bound({i + 1, 0});
				it--;
				array<int, 3> v = *it;
				qq.push_back({1, v[0], v[1], k - v[2]});
				s.erase(it);
				if (v[0] <= i - 1) {
					s.insert({v[0], i - 1, k});
				}
				if (i + 1 <= v[1]) {
					s.insert({i + 1, v[1], k});
				}
			} else {
				int l = i, r = i;
				auto it = s.lower_bound({i + 1, 0, k});
				if (it != s.end() && (*it)[0] == i + 1) {
					r = (*it)[1];
					qq.push_back({1, (*it)[0], (*it)[1], k - (*it)[2]});
					it = s.erase(it);
				}
				if (it != s.begin() && (*(--it))[1] == i - 1) {
					l = (*it)[0];
					qq.push_back({1, (*it)[0], (*it)[1], k - (*it)[2]});
					s.erase(it);
				}
				s.insert({l, r, k});
			}
			arr[i] = !(arr[i] - '0') + '0';
		} else {
			int a, b;
			cin >> a >> b;
			a--, b -= 2;
			qq.push_back({0, a, b, k});
			auto it = s.lower_bound({a + 1, 0});
			if (it != s.begin()) {
				it--;
				if (b <= (*it)[1]) {
					ans[k] += k - (*it)[2];
				}
			}
		}
	}
	solve(0, qq.size() - 1, qq);
	for (int k = 1; k <= q; k++) {
		if (ans[k] == -1) continue;
		cout << ans[k] << '\n';
	}
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14992 KB Output is correct
3 Correct 5 ms 14940 KB Output is correct
4 Correct 4 ms 14940 KB Output is correct
5 Correct 5 ms 14860 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 5 ms 14940 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 31288 KB Output is correct
2 Correct 541 ms 31916 KB Output is correct
3 Correct 700 ms 33712 KB Output is correct
4 Correct 821 ms 42572 KB Output is correct
5 Correct 955 ms 43132 KB Output is correct
6 Correct 875 ms 49448 KB Output is correct
7 Correct 595 ms 38360 KB Output is correct
8 Correct 599 ms 39116 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 5 ms 14936 KB Output is correct
3 Correct 5 ms 14940 KB Output is correct
4 Correct 4 ms 14940 KB Output is correct
5 Correct 757 ms 36556 KB Output is correct
6 Correct 988 ms 41308 KB Output is correct
7 Correct 1072 ms 41308 KB Output is correct
8 Correct 710 ms 40164 KB Output is correct
9 Correct 244 ms 27632 KB Output is correct
10 Correct 270 ms 33240 KB Output is correct
11 Correct 273 ms 32428 KB Output is correct
12 Correct 720 ms 38344 KB Output is correct
13 Correct 737 ms 40108 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14936 KB Output is correct
2 Correct 5 ms 15188 KB Output is correct
3 Correct 5 ms 14940 KB Output is correct
4 Correct 4 ms 14940 KB Output is correct
5 Correct 820 ms 44076 KB Output is correct
6 Correct 895 ms 48076 KB Output is correct
7 Correct 922 ms 49040 KB Output is correct
8 Correct 858 ms 42184 KB Output is correct
9 Correct 583 ms 37404 KB Output is correct
10 Correct 475 ms 32948 KB Output is correct
11 Correct 574 ms 36752 KB Output is correct
12 Correct 467 ms 32060 KB Output is correct
13 Correct 559 ms 35972 KB Output is correct
14 Correct 455 ms 32512 KB Output is correct
15 Correct 729 ms 38296 KB Output is correct
16 Correct 737 ms 41192 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14992 KB Output is correct
3 Correct 5 ms 14940 KB Output is correct
4 Correct 4 ms 14940 KB Output is correct
5 Correct 5 ms 14860 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 5 ms 14940 KB Output is correct
8 Correct 476 ms 31288 KB Output is correct
9 Correct 541 ms 31916 KB Output is correct
10 Correct 700 ms 33712 KB Output is correct
11 Correct 821 ms 42572 KB Output is correct
12 Correct 955 ms 43132 KB Output is correct
13 Correct 875 ms 49448 KB Output is correct
14 Correct 595 ms 38360 KB Output is correct
15 Correct 599 ms 39116 KB Output is correct
16 Correct 4 ms 14940 KB Output is correct
17 Correct 5 ms 14936 KB Output is correct
18 Correct 5 ms 14940 KB Output is correct
19 Correct 4 ms 14940 KB Output is correct
20 Correct 757 ms 36556 KB Output is correct
21 Correct 988 ms 41308 KB Output is correct
22 Correct 1072 ms 41308 KB Output is correct
23 Correct 710 ms 40164 KB Output is correct
24 Correct 244 ms 27632 KB Output is correct
25 Correct 270 ms 33240 KB Output is correct
26 Correct 273 ms 32428 KB Output is correct
27 Correct 720 ms 38344 KB Output is correct
28 Correct 737 ms 40108 KB Output is correct
29 Correct 5 ms 14936 KB Output is correct
30 Correct 5 ms 15188 KB Output is correct
31 Correct 5 ms 14940 KB Output is correct
32 Correct 4 ms 14940 KB Output is correct
33 Correct 820 ms 44076 KB Output is correct
34 Correct 895 ms 48076 KB Output is correct
35 Correct 922 ms 49040 KB Output is correct
36 Correct 858 ms 42184 KB Output is correct
37 Correct 583 ms 37404 KB Output is correct
38 Correct 475 ms 32948 KB Output is correct
39 Correct 574 ms 36752 KB Output is correct
40 Correct 467 ms 32060 KB Output is correct
41 Correct 559 ms 35972 KB Output is correct
42 Correct 455 ms 32512 KB Output is correct
43 Correct 729 ms 38296 KB Output is correct
44 Correct 737 ms 41192 KB Output is correct
45 Correct 233 ms 24768 KB Output is correct
46 Correct 334 ms 24952 KB Output is correct
47 Correct 528 ms 30196 KB Output is correct
48 Correct 864 ms 44232 KB Output is correct
49 Correct 330 ms 31916 KB Output is correct
50 Correct 310 ms 32452 KB Output is correct
51 Correct 320 ms 35080 KB Output is correct
52 Correct 307 ms 34232 KB Output is correct
53 Correct 314 ms 34492 KB Output is correct
54 Correct 310 ms 34744 KB Output is correct