Submission #207908

#	Time	Username	Problem	Language	Result	Execution time	Memory
207908		Segtree	Street Lamps (APIO19_street_lamps)	C++14	0 / 100	592 ms	22568 KiB

street_lamps

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#define N 300010
ll dat[2*N];
void init(){
	rep(i,2*N)dat[i]=0;
}
void upd(ll i,ll x){
	i+=N;
	dat[i]=x;
	for(;i;i>>=1){
		dat[i/2]=max(dat[i],dat[i^1]);
	}
}
ll qry(ll l,ll r){
	l+=N,r+=N+1;
	ll res=0;
	for(ll a=l,b=r;a<b;a>>=1,b>>=1){
		if(a&1)chmax(res,dat[a++]);
		if(b&1)chmax(res,dat[--b]);
	}
	return res;
}
ll n,q;
string typ[N];
ll a[N],b[N],x[N];
ll ti[N];
int main(){
	cin>>n>>q;
	string s;
	cin>>s;
	rep(i,n){
		if(s[i]=='1')ti[i]=0;
		else ti[i]=1e17;
	}
	init();
	for(int i=1;i<=q;i++){
		cin>>typ[i];
		if(typ[i]=="toggle"){
			cin>>x[i];
			x[i]--;
			if(ti[x[i]]==1e17){
				ti[x[i]]=i;
				upd(x[i],i);
			}
		}
		else{
			cin>>a[i]>>b[i];
			a[i]--,b[i]--;
			ll res=qry(a[i],b[i]-1);
			ll ans=i-res;
			if(ans<0)ans=0;
			cout<<ans<<endl;
		}
	}
	
}

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