Submission #597524

#	Time	Username	Problem	Language	Result	Execution time	Memory
597524		WongChun1234	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	855 ms	12672 KiB

street_lamps

#include<bits/stdc++.h>
using namespace std;
const int N=300050;
int n,q,a,b,ch[N],curr[N],lst[N],seg[N<<2];
string ipt,tmp;
void build(int id,int l,int r){
	if (l==r){
		seg[id]=(ipt[l-1]=='1')?0:INT_MAX;
		return;
	}
	int mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	seg[id]=max(seg[id*2],seg[id*2+1]);
}
void modify(int id,int l,int r,int ql,int val){
	if (l>ql||r<ql) return;
	if (l==r){
		seg[id]=val;
		return;
	}
	int mid=(l+r)/2;
	modify(id*2,l,mid,ql,val);
	modify(id*2+1,mid+1,r,ql,val);
	seg[id]=max(seg[id*2],seg[id*2+1]);
}
int query(int id,int l,int r,int ql,int qr){
	if (l>qr||r<ql) return 0;
	if (l>=ql&&r<=qr) return seg[id];
	int mid=(l+r)/2;
	return max(query(id*2,l,mid,ql,qr),query(id*2+1,mid+1,r,ql,qr));
}
int main(){
	cin>>n>>q;
	cin>>ipt;
	build(1,1,n);
	for (int i=1;i<=q;i++){
		cin>>tmp;
		if (tmp[0]=='t'){
			cin>>a;
			modify(1,1,n,a,i);
		}else{
			cin>>a>>b;
			cout<<max(0,i-query(1,1,n,a,b-1))<<"\n";
		}
	}
}

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