oj.uz

Submission #207911

# Submission time Handle Problem Language Result Execution time Memory
207911 2020-03-09T11:54:23 Z Segtree Street Lamps (APIO19_street_lamps) C++14
20 / 100
 1149 ms 30080 KB 
#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;
	init();
	rep(i,n){
		if(s[i]=='1')ti[i]=0;
		else ti[i]=1e17;
		upd(i,ti[i]);
	}
	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.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 14456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 613 ms 22648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 14 ms 14456 KB Output is correct
3 Correct 16 ms 14456 KB Output is correct
4 Correct 18 ms 14584 KB Output is correct
5 Correct 396 ms 28568 KB Output is correct
6 Correct 629 ms 29332 KB Output is correct
7 Correct 845 ms 29844 KB Output is correct
8 Correct 1140 ms 29904 KB Output is correct
9 Correct 755 ms 22392 KB Output is correct
10 Correct 815 ms 22776 KB Output is correct
11 Correct 850 ms 23032 KB Output is correct
12 Correct 1149 ms 28536 KB Output is correct
13 Correct 1143 ms 30080 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14456 KB Output is correct
2 Incorrect 15 ms 14456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 14456 KB Output isn't correct
2 Halted 0 ms 0 KB -