oj.uz

Submission #139611

# Submission time Handle Problem Language Result Execution time Memory
139611 2019-08-01T07:28:56 Z FedericoS Street Lamps (APIO19_street_lamps) C++14
40 / 100
 788 ms 19752 KB 
#include <iostream>
#include <vector>
using namespace std;
typedef pair<int,int> pii;

bool sub1=true;
bool sub2=false;

int N,Q;
char c;
string s;
int A[300005],B[300005];
bool P[300005];

bool T[105][105];

vector<pii> V[300005];

int INF=1e9;
int R[1200005];

void update(int a, int b, int k=1, int l=0, int r=N-1){
	if(l==r)
		R[k]=b;
	else{
		int m=(l+r)/2;
		if(a<=m)
			update(a,b,2*k,l,m);
		else
			update(a,b,2*k+1,m+1,r);
		R[k]=max(R[2*k],R[2*k+1]);
	}
}

int query(int a, int b, int k=1, int l=0, int r=N-1){
	if(b<l or r<a)
		return -1;
	else if(a<=l and r<=b)
		return R[k];
	else{
		int m=(l+r)/2;
		return max(query(a,b,2*k,l,m),query(a,b,2*k+1,m+1,r));
	}
}

int main(){
	cin>>N>>Q;
	for(int i=0;i<N;i++){
		cin>>c;
		P[i]=(c=='1');
		if(N<=100 and Q<=100)
			T[0][i]=P[i];
	}

	for(int i=1;i<Q+1;i++){
		cin>>s;
		if(s=="query"){
			cin>>A[i]>>B[i];
			A[i]--;
			B[i]--;
			if(B[i]-A[i]!=1)
				sub2=false;
		}
		else{
			cin>>A[i];
			A[i]--;
			B[i]=-1;
		}
	}

	if(sub1 and N<=100 and Q<=100){
		for(int i=1;i<Q+1;i++){
			if(B[i]==-1)
				T[i][A[i]]=true;
			else{
				int ans=0;
				for(int k=0;k<i;k++){
					bool flag=true;
					for(int j=A[i];j<B[i];j++)
						flag&=T[k][j];
					ans+=flag;
				}
				cout<<ans<<"\n";
			}
			for(int j=0;j<N;j++)
				T[i][j]^=T[i-1][j];
		}
	}
	else if(sub2){

		for(int j=0;j<N;j++)
			V[j].push_back({0,0});

		for(int i=1;i<Q+1;i++){

			int k=A[i];

			if(B[i]==-1){

				if(P[k])
					V[k].push_back({i,V[k].back().second+i-V[k].back().first});
				else
					V[k].push_back({i,V[k].back().second});

				P[k]=!P[k];
			}
			else{

				if(P[k])
					cout<<V[k].back().second+i-V[k].back().first<<"\n";
				else
					cout<<V[k].back().second<<"\n";
			}
		}
	}
	else{

		for(int j=0;j<N;j++){
			if(!P[j])
				update(j,INF);
			else
				update(j,0);
		}

		for(int i=1;i<Q+1;i++){
			if(B[i]==-1)
				update(A[i],i);
			else
				cout<<max(0,i-query(A[i],B[i]-1))<<"\n";
		}
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 10 ms 7336 KB Output is correct
6 Correct 10 ms 7416 KB Output is correct
7 Correct 11 ms 7416 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 367 ms 10260 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 12 ms 7416 KB Output is correct
2 Correct 13 ms 7416 KB Output is correct
3 Correct 11 ms 7416 KB Output is correct
4 Correct 12 ms 7416 KB Output is correct
5 Correct 550 ms 14200 KB Output is correct
6 Correct 591 ms 18936 KB Output is correct
7 Correct 682 ms 19392 KB Output is correct
8 Correct 788 ms 19752 KB Output is correct
9 Correct 324 ms 13048 KB Output is correct
10 Correct 354 ms 13540 KB Output is correct
11 Correct 362 ms 13660 KB Output is correct
12 Correct 750 ms 18200 KB Output is correct
13 Correct 752 ms 19360 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 10 ms 7336 KB Output is correct
6 Correct 10 ms 7416 KB Output is correct
7 Correct 11 ms 7416 KB Output is correct
8 Incorrect 367 ms 10260 KB Output isn't correct
9 Halted 0 ms 0 KB -