Submission #1203210

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203210		Johan	Street Lamps (APIO19_street_lamps)	C++20	0 / 100	5090 ms	1768 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 6;
const int INF = 1e18;
int a[N], st[N * 4];
void upd(int v, int l, int r, int pos, int val){
	if(l == r){
		st[v] = st[v] ^ val;
		return;
	}
	int mid = (l + r) >> 1;
	if(mid >= pos)
		upd(v * 2, l, mid, pos, val);
	else
		upd(v * 2 + 1, mid + 1, r, pos, val);
	st[v] = min(st[v * 2], st[v * 2 + 1]);
}
int ask(int v, int l, int r, int ql, int qr){
	if(l > qr || r < ql)	return INF;
	if(l >= ql && r <= qr)	return st[v];
	int mid = (l + r) >> 1;
	return min(ask(v * 2, l, mid, ql, qr), ask(v * 2 + 1, mid + 1, r, ql, qr));
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, q;
	string s;
	cin >> n >> q >> s;
	s = '#' + s;
	for(int i = 1; i <= n; i++){
		a[i] = (int)(s[i] - '0');
		upd(1, 1, n, i, a[i]);	
	}
	vector < pair < string , pair < int , int > > > Q;
	while(q--){
		string type;
		cin >> type;
		if(type == "query"){
			int l, r, ans = 0;
			cin >> l >> r;
			vector < int > qq;
			Q.push_back({type, {l, r}});	
			reverse(Q.begin(), Q.end());
			for(auto i : Q){
				if(i.second.second == -1){
					upd(1, 1, n, i.second.first, 1);
					qq.push_back(i.second.first);	
				}
				else
					ans += ask(1, 1, n, l, r);
			}
			reverse(Q.begin(), Q.end());
			for(auto i : qq)
				upd(1, 1, n, i, 1);
			cout << ans << endl;
		}
		else {
			int pos;
			cin >> pos;
			upd(1, 1, n, pos, 1);
			Q.push_back({type, {pos, -1}});
		}	
	}
}

Compilation message (stderr)

street_lamps.cpp:4:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    4 | const int INF = 1e18;
      |                 ^~~~

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