oj.uz

Submission #396595

# Submission time Handle Problem Language Result Execution time Memory
396595 2021-04-30T11:25:19 Z mosiashvililuka Street Lamps (APIO19_street_lamps) C++14
60 / 100
 723 ms 26916 KB 
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,f[300009],pas,sub2,fx[300009],fx2[300009],ans[300009],sub3,za,seg[1200009],l,r;
pair <string, pair <int, int> > p[300009];
string S;
int els(int q){
	if(q==0) return 1; else return 0;
}
void read(int q, int w, int rr){
	if(q>r||w<l) return;
	if(q>=l&&w<=r){
		pas=max(pas,seg[rr]);
		return;
	}
	read(q,(q+w)/2,rr*2);
	read((q+w)/2+1,w,rr*2+1);
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>tes;
	cin>>S;
	S.insert(0,"0");
	p[0].first="W";
	for(i=1; i<=a; i++){
		f[i]=S[i]-'0';
	}
	a++;
	for(t=1; t<=tes; t++){
		cin>>p[t].first;
		if(p[t].first[0]=='q'){
			cin>>p[t].second.first>>p[t].second.second;
		}else{
			cin>>p[t].second.first;
		}
	}
	
	//N3
		sub3=0;
	for(i=1; i<a; i++){
		fx[i]=f[i];
	}
	for(t=1; t<=tes; t++){
		if(p[t].first[0]=='t'){
			if(fx[p[t].second.first]==1){
				sub3=1;
				break;
			}
			fx[p[t].second.first]=1;
		}
	}
	if(sub3==0){
		za=1;
		while(za<a) za*=2;
		for(i=1; i<=za*2; i++){
			seg[i]=tes+3;
		}
		for(i=1; i<a; i++){
			if(f[i]==1){
				c=i+za-1;
				seg[c]=0;
				c/=2;
				while(c!=1){
					seg[c]=max(seg[c*2],seg[c*2+1]);
					c/=2;
				}
			}
		}
		for(t=1; t<=tes; t++){
			if(p[t].first[0]=='t'){
				c=p[t].second.first+za-1;
				seg[c]=t;
				c/=2;
				while(c!=1){
					seg[c]=max(seg[c*2],seg[c*2+1]);
					c/=2;
				}
			}else{
				l=p[t].second.first;r=p[t].second.second-1;
				pas=0;
				read(1,za,1);
				cout<<max(0,t-pas)<<endl;
			}
		}
		return 0;
	}
	
	
	
//	N2
	sub2=0;
	for(t=1; t<=tes; t++){
		if(p[t].first[0]=='q'){
			if(p[t].second.second!=p[t].second.first+1){
				sub2=1;
				break;
			}
		}
	}
	if(sub2==0){
		for(i=1; i<=a; i++){
			if(f[i]==1){
				fx[i]=0;
				fx2[i]=1;
			}
		}
		for(t=1; t<=tes; t++){
			if(p[t].first[0]=='t'){
				c=p[t].second.first;
				if(fx2[c]==0){
					fx[c]=t;
					fx2[c]=1;
				}else{
					ans[c]+=t-fx[c];
					fx2[c]=0;
				}
			}else{
				c=p[t].second.first;
				if(fx2[c]==0){
					cout<<ans[p[t].second.first]<<endl;
				}else{
					cout<<ans[p[t].second.first]+t-fx[c]<<endl;
				}
			}
		}
		return 0;
	}
	
	if(a<=102&&tes<=102){
		for(i=1; i<=tes; i++){
			if(p[i].first[0]=='t'){
				f[p[i].second.first]=els(f[p[i].second.first]);
				continue;
			}
			pas=0;
			for(ii=i-1; ii>=0; ii--){
				for(j=p[i].second.first; j<p[i].second.second; j++){
					if(f[j]==0) break;
				}
				if(j==p[i].second.second){
					pas++;
				}
				if(p[ii].first[0]=='t'){
					f[p[ii].second.first]=els(f[p[ii].second.first]);
				}
			}
			for(ii=1; ii<=i-1; ii++){
				if(p[ii].first[0]=='t'){
					f[p[ii].second.first]=els(f[p[ii].second.first]);
				}
			}
			cout<<pas<<endl;
		}
		exit(0);
	}
	

	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Correct 7 ms 11980 KB Output is correct
3 Correct 7 ms 11980 KB Output is correct
4 Correct 7 ms 11980 KB Output is correct
5 Correct 7 ms 11980 KB Output is correct
6 Correct 8 ms 11980 KB Output is correct
7 Correct 7 ms 11980 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 12960 KB Output is correct
2 Correct 310 ms 12964 KB Output is correct
3 Correct 317 ms 13004 KB Output is correct
4 Correct 373 ms 17868 KB Output is correct
5 Correct 437 ms 19856 KB Output is correct
6 Correct 283 ms 17744 KB Output is correct
7 Correct 636 ms 19656 KB Output is correct
8 Correct 644 ms 20960 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12108 KB Output is correct
2 Correct 8 ms 12108 KB Output is correct
3 Correct 9 ms 12036 KB Output is correct
4 Correct 10 ms 12080 KB Output is correct
5 Correct 117 ms 23256 KB Output is correct
6 Correct 293 ms 23880 KB Output is correct
7 Correct 474 ms 24508 KB Output is correct
8 Correct 719 ms 26820 KB Output is correct
9 Correct 454 ms 15844 KB Output is correct
10 Correct 500 ms 15940 KB Output is correct
11 Correct 494 ms 16196 KB Output is correct
12 Correct 683 ms 25436 KB Output is correct
13 Correct 723 ms 26916 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Correct 7 ms 11980 KB Output is correct
3 Correct 7 ms 11980 KB Output is correct
4 Correct 7 ms 11980 KB Output is correct
5 Correct 7 ms 11980 KB Output is correct
6 Correct 8 ms 11980 KB Output is correct
7 Correct 7 ms 11980 KB Output is correct
8 Correct 314 ms 12960 KB Output is correct
9 Correct 310 ms 12964 KB Output is correct
10 Correct 317 ms 13004 KB Output is correct
11 Correct 373 ms 17868 KB Output is correct
12 Correct 437 ms 19856 KB Output is correct
13 Correct 283 ms 17744 KB Output is correct
14 Correct 636 ms 19656 KB Output is correct
15 Correct 644 ms 20960 KB Output is correct
16 Correct 8 ms 12108 KB Output is correct
17 Correct 8 ms 12108 KB Output is correct
18 Correct 9 ms 12036 KB Output is correct
19 Correct 10 ms 12080 KB Output is correct
20 Correct 117 ms 23256 KB Output is correct
21 Correct 293 ms 23880 KB Output is correct
22 Correct 474 ms 24508 KB Output is correct
23 Correct 719 ms 26820 KB Output is correct
24 Correct 454 ms 15844 KB Output is correct
25 Correct 500 ms 15940 KB Output is correct
26 Correct 494 ms 16196 KB Output is correct
27 Correct 683 ms 25436 KB Output is correct
28 Correct 723 ms 26916 KB Output is correct
29 Incorrect 8 ms 11980 KB Output isn't correct
30 Halted 0 ms 0 KB -