Submission #561498

#	Time	Username	Problem	Language	Result	Execution time	Memory
561498		hollwo_pelw	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	2610 ms	128016 KiB

street_lamps

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;

void Hollwo_Pelw();

signed main(){
#ifndef hollwo_pelw_local
	if (fopen(".inp", "r"))
		assert(freopen(".inp", "r", stdin)), assert(freopen(".out", "w", stdout));
#else
	using namespace chrono;
	auto start = steady_clock::now();
#endif
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = steady_clock::now();
	cout << "\nExcution time : " << duration_cast<milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}

const int N = 6e5 + 5;

struct query_t {
	int t, sx, ex, sy, ey, v;
};
vector<query_t> queries;

int n, q;
char s[N];

vector<int> bit[N], val[N];

void update_temp(int x, int y) {
	for (int px = x; px <= n; px += px & -px)
		val[px].push_back(y);
}

void update(int x, int y, int v) {
	for (int px = x; px <= n; px += px & -px) {
		int py = lower_bound(val[px].begin(), val[px].end(), y) - val[px].begin() + 1;
		for (; py < (int) bit[px].size(); py += py & -py)
			bit[px][py] += v;
	}
}

int get(int x, int y) {
	int r = 0;
	for (int px = x; px > 0; px -= px & -px) {
		int py = upper_bound(val[px].begin(), val[px].end(), y) - val[px].begin();
		for (; py; py -= py & -py)
			r += bit[px][py];
	}
	return r;
}

void update_temp(int sx, int ex, int sy, int ey, int v) {
	queries.push_back({1, sx, ex, sy, ey, v});
	update_temp(sx, sy);
	update_temp(ex + 1, sy);
	update_temp(sx, ey + 1);
	update_temp(ex + 1, ey + 1);
}

void update(int sx, int ex, int sy, int ey, int v) {
	update(sx, sy, v);
	update(sx, ey + 1, -v);
	update(ex + 1, sy, -v);
	update(ex + 1, ey + 1, v);
}

void Hollwo_Pelw(){
	cin >> n >> q >> (s + 1);

	set<int> st;

	for (int i = 1; i <= n; i++)
		if (s[i] == '0') st.insert(i);

	for (int i = 1, l, r, p; i <= q; i++) {
		string tp; cin >> tp;
		if (tp[0] == 't') {
			cin >> p;
			if (st.count(p)) {
				auto it = st.find(p);
				l =     it == st.begin() ? 1 : *prev(it) + 1;
				r = next(it) == st.end() ? n : *next(it) - 1;
				st.erase(p);
				update_temp(l, p, p, r, -i);
			} else {
				st.insert(p);
				auto it = st.find(p);
				l =     it == st.begin() ? 1 : *prev(it) + 1;
				r = next(it) == st.end() ? n : *next(it) - 1;
				update_temp(l, p, p, r, +i);
			}
		}
		if (tp[0] == 'q') {
			cin >> l >> r, -- r;
			auto it = st.lower_bound(l);
			int v = it == st.end() || *it > r ? i : 0;
			queries.push_back({0, l, l, r, r, v});
		}
	}

	for (int i = 1; i <= n; i++) {
		sort(val[i].begin(), val[i].end());
		val[i].erase(unique(val[i].begin(), val[i].end()), val[i].end());
		bit[i].resize(val[i].size() + 5);
	}

	for (auto [t, sx, ex, sy, ey, v] : queries) {
		if (t) {
			update(sx, ex, sy, ey, v);
		} else {
			cout << v + get(sx, sy) << '\n';
		}
	}
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20