Submission #1192045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192045		Tsagana	Street Lamps (APIO19_street_lamps)	C++20	100 / 100	2284 ms	55968 KiB

street_lamps

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

const int N = 3e5+5;
const int mod = 1e9+7;

int n, q, k, a[N], ans, cnt;
vector<array<int, 3>> tree[4*N];
string s;

void find(int l, int r, int L = 1, int R = n, int id = 1) {
	for (auto x : tree[id]) {
		if (x[0] <= r && r <= x[1]) 
			{ans += x[2]; cnt++;}
	}
	
	int M = (L + R) / 2, x = 2 * id, y = x + 1;
	if (L == R) return ;
	if (l <= M) find(l, r, L, M, x);
	else find(l, r, M + 1, R, y);
}

void add(int l, int r, array<int, 3> v, int L = 1, int R = n, int id = 1) {
	if (L > r || l > R) return ;
	if (L >= l && R <= r) {tree[id].pb(v); return ;}
	int M = (L + R) / 2, x = 2 * id, y = x + 1;
	add(l, r, v, L, M, x), add(l, r, v, M + 1, R, y);
}

void solve () {
	cin >> n >> q >> s;
	
	set<int> ss;
	s = "$" + s;
	for (int i = 1; i <= n; i++) {
		a[i] = s[i] - '0';
		if (!a[i]) ss.insert(i);
	}
	
	for (int i = 1; i <= n; i++) {
		if (!a[i]) continue ;
		int j = i;
		while (j <= n && a[j] == a[i]) j++;
		j--, add(i, j, {i, j, 0}), i = j;
	}

	for (int i = 1; i <= q; i++) {
		cin >> s;
		if (s == "query") {
			int a, b; cin >> a >> b, b--; 
			ans = 0, cnt = 0, find(a, b);
			if (cnt & 1) ans += i;
			cout << ans << "\n";
		}
		else {
			int m; cin >> m;
			if (a[m]) {
				auto L = ss.lb(m);
				auto R = ss.ub(m);
				int r = (L == ss.end() ? n + 1 : *L);	
				int l = (R == ss.begin() ? 0 : *--R);
				add(l+1, m, {m, r-1, i}), ss.insert(m);
			}
			else {
				ss.erase(m);
				auto L = ss.lb(m);
				auto R = ss.ub(m);
				int r = (L == ss.end() ? n + 1 : *L);	
				int l = (R == ss.begin() ? 0 : *--R);
				add(l+1, m, {m, r-1, -i});
			}
			a[m] ^= 1;
		}
	}
}
signed main() {IOS solve(); return 0;}

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