oj.uz

답안 #335122

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
335122 2020-12-11T08:06:12 Z nicholask 가로등 (APIO19_street_lamps) C++14
20 / 100
 1194 ms 14096 KB 
#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.0

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

Subtask #2
0 / 20.0

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

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 4 ms 364 KB Output is correct
5 Correct 288 ms 10376 KB Output is correct
6 Correct 549 ms 10952 KB Output is correct
7 Correct 850 ms 11724 KB Output is correct
8 Correct 1194 ms 14040 KB Output is correct
9 Correct 749 ms 4024 KB Output is correct
10 Correct 810 ms 4460 KB Output is correct
11 Correct 811 ms 4780 KB Output is correct
12 Correct 1134 ms 12680 KB Output is correct
13 Correct 1153 ms 14096 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 364 KB Output is correct
2 Incorrect 3 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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