Submission #1191333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191333		dubabuba	Street Lamps (APIO19_street_lamps)	C++20	20 / 100	348 ms	7464 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;

const int mxn = 3e5 + 10;
int n, q, sus[mxn * 4];
string s;

void upt(int id, int tl, int tr, int i, int x) {
	if(tl == tr) {
		sus[id] = x;
		return;
	}
	int tm = (tl + tr) / 2;
	if(i <= tm) upt(id * 2 + 1, tl, tm, i, x);
	else upt(id * 2 + 2, tm + 1, tr, i, x);
	sus[id] = max(sus[id * 2 + 1], sus[id * 2 + 2]);
}

int query(int id, int tl, int tr, int l, int r) {
	if(tl == l && r == tr) return sus[id];
	int tm = (tl + tr) / 2;
	if(r <= tm) return query(id * 2 + 1, tl, tm, l, r);
	if(tm < l) return query(id * 2 + 2, tm + 1, tr, l, r);
	int LQ = query(id * 2 + 1, tl, tm, l, tm);
	int RQ = query(id * 2 + 2, tm + 1, tr, tm + 1, r);
	return max(LQ, RQ);
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

	cin >> n >> q >> s;
	memset(sus, 0x3f, sizeof sus);
	for(int i = 0; i < n; i++) {
		if(s[i] == '1')
			upt(0, 0, n - 1, i, 0);	
	}

	for(int TIME = 1; TIME <= q; TIME++) {
		string type;
		cin >> type;

		if(type == "toggle") {
			int id;
			cin >> id;
			id--;

			assert(id < n);
			upt(0, 0, n - 1, id, TIME);
		}
		else {
			int l, r;
			cin >> l >> r;
			l--, r--;

			assert(l < r);
			int q = query(0, 0, n - 1, l, r - 1);
			q = TIME - q;

			cout << max(0, q) << endl;
		}
	}
	return 0;
}

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