oj.uz

Submission #902464

# Submission time Handle Problem Language Result Execution time Memory
902464 2024-01-10T12:57:28 Z Trisanu_Das Street Lamps (APIO19_street_lamps) C++17
60 / 100
 363 ms 29900 KB 
#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.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 18512 KB Output is correct
2 Correct 147 ms 18908 KB Output is correct
3 Correct 170 ms 19724 KB Output is correct
4 Correct 247 ms 29132 KB Output is correct
5 Correct 253 ms 28400 KB Output is correct
6 Correct 284 ms 29268 KB Output is correct
7 Correct 269 ms 28616 KB Output is correct
8 Correct 286 ms 29900 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10844 KB Output is correct
2 Correct 3 ms 10840 KB Output is correct
3 Correct 3 ms 10844 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 210 ms 19056 KB Output is correct
6 Correct 258 ms 19596 KB Output is correct
7 Correct 298 ms 20328 KB Output is correct
8 Correct 363 ms 22516 KB Output is correct
9 Correct 156 ms 15924 KB Output is correct
10 Correct 157 ms 16596 KB Output is correct
11 Correct 166 ms 16564 KB Output is correct
12 Correct 337 ms 21232 KB Output is correct
13 Correct 346 ms 22688 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 11096 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 131 ms 18512 KB Output is correct
9 Correct 147 ms 18908 KB Output is correct
10 Correct 170 ms 19724 KB Output is correct
11 Correct 247 ms 29132 KB Output is correct
12 Correct 253 ms 28400 KB Output is correct
13 Correct 284 ms 29268 KB Output is correct
14 Correct 269 ms 28616 KB Output is correct
15 Correct 286 ms 29900 KB Output is correct
16 Correct 3 ms 10844 KB Output is correct
17 Correct 3 ms 10840 KB Output is correct
18 Correct 3 ms 10844 KB Output is correct
19 Correct 3 ms 10844 KB Output is correct
20 Correct 210 ms 19056 KB Output is correct
21 Correct 258 ms 19596 KB Output is correct
22 Correct 298 ms 20328 KB Output is correct
23 Correct 363 ms 22516 KB Output is correct
24 Correct 156 ms 15924 KB Output is correct
25 Correct 157 ms 16596 KB Output is correct
26 Correct 166 ms 16564 KB Output is correct
27 Correct 337 ms 21232 KB Output is correct
28 Correct 346 ms 22688 KB Output is correct
29 Correct 3 ms 10844 KB Output is correct
30 Incorrect 3 ms 11096 KB Output isn't correct
31 Halted 0 ms 0 KB -