#include <bits/stdc++.h>
#define forf(i,a,b) for(int i = a; i<=b; i++)
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
int N,M,Q;
char S[300001];
struct Interval{
int s,e,ts,te;
}; vector<Interval> ints;
map<int,int> stkeyf,stkeyb;
map<int,int> enkeyf,enkeyb;
void ins(int s, int e, int t){
int now = ints.size();
ints.push_back({s,e, t, -1});
stkeyf.insert({s, now});
stkeyb.insert({-s, now});
enkeyf.insert({e, now});
enkeyb.insert({-e, now});
}
void ers(int ind ,int t){
ints[ind].te = t;
int a = ints[ind].s;
int b = ints[ind].e;
stkeyf.erase(stkeyf.lower_bound(a));
stkeyb.erase(stkeyb.lower_bound(-a));
enkeyf.erase(enkeyf.lower_bound(b));
enkeyb.erase(enkeyb.lower_bound(-b));
}
struct Event{
int t;
int q;
int s,e,v;
bool operator<(const Event &r) const{
if(t==r.t){
if(q==r.q) return s<r.s;
return q>r.q;
}
return t<r.t;
}
}; vector<Event> events;
int isq[300001];
int ans[300001];
void dnc(int s, int e){
int m = s+e>>1;
forf(i,s,e){
forf(j,i+1,e){
if(events[i].q == 0 && events[j].q == 1){
if(events[i].s <= events[j].s && events[j].e <= events[i].e){
ans[events[j].t] += events[i].v;
}
}
}
}
return;
dnc(s,m);
dnc(m+1,e);
}
int main(){
scanf("%d %d" , &N,&Q);
scanf("%s" ,S); S[N] = '0';
{
int l = 1;
forf(i, 1, N) {
if (S[i - 1] == '0' && S[i] == '1') l = i+1;
if (S[i - 1] == '1' && S[i] == '0') {
ins(l,i,1);
}
}
}
forf(i,2,Q+1){ // t = i
char s[10]; int a,b;
scanf("%s" , s);
if(s[0] == 'q'){
isq[i] = 1;
scanf("%d %d" , &a,&b); b--;
events.push_back({i,1,a,b});
if(enkeyf.lower_bound(b) != enkeyf.end()) {
int ind = enkeyf.lower_bound(b)->second;
if (ints[ind].s <= a && b <= ints[ind].e) ans[i] += (i - ints[ind].ts);
}
}
else{
scanf("%d" , &a);
if(S[a-1] == '0'){
S[a-1] = '1';
int l = a, r = a;
if(enkeyb.lower_bound(-a) != enkeyb.end()) {
int indl = enkeyb.lower_bound(-a)->second;
if (ints[indl].e + 1 == a) {
ers(indl, i - 1);
l = ints[indl].s;
}
}
if(stkeyf.lower_bound(a) != stkeyf.end()) {
int indr = stkeyf.lower_bound(a)->second;
if (ints[indr].s - 1 == a) {
ers(indr, i - 1);
r = ints[indr].e;
}
}
ins(l,r,i);
}
else{
S[a-1] = '0';
int ind = enkeyf.lower_bound(a)->second;
ers(ind,i-1);
if(ints[ind].s < a) ins(ints[ind].s , a-1 , i);
if(ints[ind].e > a) ins(a+1 , ints[ind].e , i);
}
}
}
for(auto i : ints){
if(i.te != -1) events.push_back({i.te,0,i.s,i.e,i.te-i.ts+1});
}
sort(all(events));
dnc(0,events.size()-1);
forf(i,1,Q+1){
if(isq[i]) printf("%d\n" , ans[i]);
}
}
Compilation message
street_lamps.cpp: In function 'void dnc(int, int)':
street_lamps.cpp:49:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
49 | int m = s+e>>1;
| ~^~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | scanf("%d %d" , &N,&Q);
| ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
66 | scanf("%s" ,S); S[N] = '0';
| ~~~~~^~~~~~~~~
street_lamps.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%s" , s);
| ~~~~~^~~~~~~~~~
street_lamps.cpp:83:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | scanf("%d %d" , &a,&b); b--;
| ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:91:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | scanf("%d" , &a);
| ~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5040 ms |
19952 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2648 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2652 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 5 |
Execution timed out |
5079 ms |
38092 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2500 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 5 |
Execution timed out |
5044 ms |
34680 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Execution timed out |
5040 ms |
19952 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
