Submission #902464

#	Time	Username	Problem	Language	Result	Execution time	Memory
902464		Trisanu_Das	Street Lamps (APIO19_street_lamps)	C++17	60 / 100	363 ms	29900 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
 
bool sub1 = true, sub2 = true;
 
int N, Q; 
char c; string s;
int A[300005], B[300005], R[1200005];
bool P[300005], T[105][105];
vector<pii> V[300005];
int INF=1e9;

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]--;
		}
	}
	if(sub1 && N <= 100 && 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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20