oj.uz

답안 #207911

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
207911 2020-03-09T11:54:23 Z Segtree 가로등 (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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 14456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 613 ms 22648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 14456 KB Output isn't correct
2 Halted 0 ms 0 KB -