Submission #335122

#	Time	Username	Problem	Language	Result	Execution time	Memory
335122		nicholask	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	1194 ms	14096 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
int a[300010];
int seg[1200010];
void build(int v,int tl,int tr){
	if (tl==tr){
		seg[v]=a[tl];
		return;
	}
	int tm=(tl+tr)>>1;
	build(v+v,tl,tm);
	build(v+v+1,tm+1,tr);
	seg[v]=max(seg[v+v],seg[v+v+1]);
}
void update(int v,int tl,int tr,int pos,int val){
	if (tl==tr){
		seg[v]=val;
		return;
	}
	int tm=(tl+tr)>>1;
	if (pos<=tm) update(v+v,tl,tm,pos,val);
	else update(v+v+1,tm+1,tr,pos,val);
	seg[v]=max(seg[v+v],seg[v+v+1]);
}
int query(int v,int tl,int tr,int l,int r){
	if (l>r) return 0;
	if (tl==l&&tr==r) return seg[v];
	int tm=(tl+tr)>>1;
	if (r<=tm) return query(v+v,tl,tm,l,r);
	if (l>tm) return query(v+v+1,tm+1,tr,l,r);
	return max(query(v+v,tl,tm,l,tm),query(v+v+1,tm+1,tr,tm+1,r));
}
int main(){
	int n,q;
	cin>>n>>q;
	string s;
	cin>>s;
	for (int i=1; i<=n; i++){
		if (s[i-1]=='1') a[i]=0;
		else a[i]=1e9;
	}
	build(1,1,n);
	for (int z=1; z<=q; z++){
		string temp;
		cin>>temp;
		if (temp=="toggle"){
			int u;
			cin>>u;
			update(1,1,n,u,z);
		} else {
			int u,v;
			cin>>u>>v;
			int ans=query(1,1,n,u,v-1);
			if (ans==1e9) cout<<0;
			else cout<<z-ans;
			cout<<endl;
		}
	}
}

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