#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
int N, Q;
int A[303030];
bool chk[303030];
int ans[303030];
struct Sq{
int x, y, t;
bool operator<(const Sq &r)const{
if (x == r.x) return y < r.y;
return x < r.x;
}
};
set<Sq> S;
vector<Sq> V, L;
int T[303030];
void update(int k, int v){
while (k<=N){
T[k] += v;
k += k & -k;
}
}
int read(int k){
int ret;
while (k){
ret += T[k];
k ^= k & -k;
}
return ret;
}
void sweep(){
for (Sq it : L){
if (it.t < 0) ans[-it.t] += read(it.y);
else if (it.x <= it.y){
update(it.x, it.t);
update(it.y+1, -it.t);
}
else{
update(it.y, it.t);
update(it.x, -it.t);
}
}
for (Sq it : L){
if (it.t < 0) continue;
if (it.x <= it.y){
update(it.x, -it.t);
update(it.y+1, it.t);
}
else{
update(it.y, -it.t);
update(it.x, it.t);
}
}
}
void DNC(int s, int e){
if (s >= e) return;
int mid = (s+e)/2;
DNC(s, mid);
DNC(mid+1, e);
for (int i=s; i<=mid; i++) if (V[i].t > 0){
L.push_back((Sq){V[i].x, V[i].y, V[i].t});
L.push_back((Sq){V[i].y+1, V[i].x, V[i].t});
}
for (int i=mid+1; i<=e; i++) if (V[i].t < 0) L.push_back((Sq){V[i].x, V[i].y, V[i].t});
sort(L.begin(), L.end(), [&](Sq a, Sq b){
if (a.x == b.x) return a.t > b.t;
return a.x < b.x;
});
sweep();
L.clear();
}
int main(){
scanf("%d %d", &N, &Q);
int s=0;
for (int i=1; i<=N; i++){
scanf("%1d", &A[i]);
if (A[i] && !s) s = i;
if (!A[i] && s) {
S.insert((Sq){s, i-1, 0});
s = 0;
}
}
if (s) S.insert((Sq){s, N, 0});
char str[10];
for (int i=1; i<=Q; i++){
scanf("%s", str+1);
if (str[1] == 't'){
int k;
scanf("%d", &k);
if (A[k]){
auto it = --S.lower_bound((Sq){k, N+1, 0});
Sq a = *it;
S.erase(it);
V.push_back((Sq){a.x, a.y, i-a.t});
if (a.x != k) S.insert((Sq){a.x, k-1, i});
if (a.y != k) S.insert((Sq){k+1, a.y, i});
A[k] = 0;
}
else{
auto it = S.lower_bound((Sq){k, N+1, 0});
if (A[k-1] && A[k+1]){
auto pr = it;
Sq a = *it;
Sq b = *(--pr);
S.erase(it), S.erase(pr);
V.push_back((Sq){a.x, a.y, i-a.t});
V.push_back((Sq){b.x, b.y, i-b.t});
S.insert((Sq){b.x, a.y, i});
}
else if (A[k-1]){
Sq a = *(--it);
S.erase(it);
V.push_back((Sq){a.x, a.y, i-a.t});
S.insert((Sq){a.x, a.y+1, i});
}
else if (A[k+1]){
Sq a = *it;
S.erase(it);
V.push_back((Sq){a.x, a.y, i-a.t});
S.insert((Sq){a.x-1, a.y, i});
}
else S.insert((Sq){k, k, i});
A[k] = 1;
}
}
else{
int x, y;
scanf("%d %d", &x, &y);
y--;
chk[i] = true;
if (A[x]){
auto it = --S.lower_bound((Sq){x, N+1, 0});
if (it->y >= y) ans[i] += i - it->t;
}
V.push_back((Sq){x, y, -i});
}
}
for (int i=1; i<=Q; i++) if (chk[i]) printf("%d\n", ans[i]);
return 0;
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &Q);
~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%1d", &A[i]);
~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", str+1);
~~~~~^~~~~~~~~~~~~
street_lamps.cpp:100:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &k);
~~~~~^~~~~~~~~~
street_lamps.cpp:139:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'int read(int)':
street_lamps.cpp:36:9: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
return ret;
^~~
street_lamps.cpp: In function 'void sweep()':
street_lamps.cpp:41:28: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
if (it.t < 0) ans[-it.t] += read(it.y);
~~~~~~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
138 ms |
10852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
