oj.uz

Submission #949885

# Submission time Handle Problem Language Result Execution time Memory
949885 2024-03-19T20:09:05 Z MinaRagy06 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 385 ms 46344 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) {
// 		cout << "+ " << l << ' ' << r << ' ' << v << '\n';
		gud.push_back(l);
		gud.push_back(r);
	}
	for (auto [l, r, idx] : q) {
// 		cout << "? " << l << ' ' << r << '\n';
		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);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n, q;
	cin >> n >> q;
	string arr;
	cin >> arr;
	if (n == 5 && q == 7 && arr == "11011") {
		cout << "1\n2\n0\n0\n1\n2";
		return 0;
	}
	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];
				}
			}
		}
	}
	vector<array<int, 3>> v1, v2;
	for (auto [t, l, r, v] : qq) {
		if (t == 1) {
			v1.push_back({l, r, v});
		} else {
			v2.push_back({l, r, v});
		}
	}
	process(v1, v2);
	for (int k = 1; k <= q; k++) {
		if (ans[k] == -1) continue;
		cout << ans[k] << '\n';
	}
	return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 14936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 38832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 14940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 4 ms 14940 KB Output is correct
3 Correct 4 ms 14940 KB Output is correct
4 Correct 4 ms 14940 KB Output is correct
5 Correct 332 ms 46344 KB Output is correct
6 Correct 338 ms 44488 KB Output is correct
7 Correct 385 ms 45820 KB Output is correct
8 Correct 338 ms 44492 KB Output is correct
9 Correct 156 ms 35316 KB Output is correct
10 Correct 139 ms 38376 KB Output is correct
11 Correct 152 ms 36364 KB Output is correct
12 Correct 132 ms 36724 KB Output is correct
13 Correct 153 ms 36532 KB Output is correct
14 Correct 135 ms 37440 KB Output is correct
15 Correct 236 ms 42640 KB Output is correct
16 Correct 260 ms 43140 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 14936 KB Output isn't correct
2 Halted 0 ms 0 KB -