#include <bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(int i = a; i < b; i++)
const int N = 3e5 + 5, M = 105;
const int RA = 1e6 + 5;
int n, q;
int a[M][M];
void subtask_1(){
f(i,1,q+1){
f(j,1,n+1) a[i][j] = a[i-1][j];
string ty;
int x, y;
cin >> ty;
if(ty[0] == 'q'){
cin >> x >> y;
// cuantos tiempos el rango [x, y-1] suma 0
int ans = 0;
f(j,0,i){
int sum = 0;
f(r,x,y) sum += a[j][r];
if(sum == 0) ans++;
}
cout << ans << "\n";
}
else{
cin >> x;
a[i][x] = 1 - a[i][x];
}
}
}
int A[RA], root[N];
vector <int> L, R, st;
int ti[RA], X[N], Y[N];
int createLeaf(int val){
L.push_back(-1), R.push_back(-1);
st.push_back(val);
return L.size() - 1;
}
int createNode(int u, int v){
L.push_back(u), R.push_back(v);
st.push_back(st[u] + st[v]);
return L.size() - 1;
}
int build(int l, int r){
if(l == r) return createLeaf(A[l]);
int m = (l+r)>>1;
return createNode(build(l, m), build(m+1, r));
}
int upd(int id, int l, int r, int pos, int val){
if(l == r) return createLeaf(val);
int m = (l+r)>>1;
if(pos <= m) return createNode(upd(L[id], l, m, pos, val), R[id]);
return createNode(L[id], upd(R[id], m+1, r, pos, val));
}
int Query(int id, int l, int r, int x, int y){
if(r < x or y < l) return 0;
if(x <= l and r <= y) return st[id];
int m = (l+r)>>1;
return Query(L[id], l, m, x, y) + Query(R[id], m+1, r, x, y);
}
void subtask_3(){
root[0] = build(1, n);
f(i,1,q+1){
root[i] = root[i-1];
if(ti[i] == 0){
int x = X[i], y = Y[i];
y--;
int ans = 0;
if(Query(root[i-1], 1, n, x, y) == 0){
int l = 0, r = i-1;
while(l < r){
int m = (l+r)>>1;
if(Query(root[m], 1, n, x, y) == 0) r = m;
else l = m+1;
}
ans = i - l;
}
cout << ans << "\n";
}
else{
int x = X[i];
root[i] = upd(root[i], 1, n, x, 0);
}
}
}
int curr[RA];
int start[RA];
void subtask_2(){
f(i,1,q+1){
if(ti[i] == 0){
// int tot = i - curr[X[i]];
// // if(A[X[i]] == 1){
// // tot -= ((i-1) - start[X[i]] + 1);
// // }
// cout << tot << "\n";
}
else{
// if(A[X[i]] == 0){
// start[X[i]] = i;
// }
// else{
// curr[X[i]] += i - start[X[i]] + 1;
// }
// A[X[i]] = 1 - A[X[i]];
}
}
}
int main(){
cin >> n >> q;
string s;
cin >> s;
f(i,0,n){
if(s[i] == '0') a[0][i+1] = A[i+1] = 1;
else a[0][i+1] = A[i+1] = 0;
}
if(n <= 100){
subtask_1();
return 0;
}
bool flag = true;
f(i,1,q+1){
string sa;
cin >> sa;
if(sa[0] == 'q'){
cin >> X[i] >> Y[i];
if(Y[i] != X[i] + 1) flag = false;
}
else{
ti[i] = 1;
cin >> X[i];
}
}
// subtask_2();
// if(flag) {
// subtask_2();
// return 0;
// }
// subtask_3();
return 0;
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:133:10: warning: variable 'flag' set but not used [-Wunused-but-set-variable]
133 | bool flag = true;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
316 KB |
Output is correct |
| 4 |
Correct |
1 ms |
312 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
316 KB |
Output is correct |
| 4 |
Correct |
1 ms |
312 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
