Submission #949886

#	Time	Username	Problem	Language	Result	Execution time	Memory
949886		MinaRagy06	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1052 ms	45112 KiB

street_lamps

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20