#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define X first
#define Y second
#define pb push_back
#define sz(x) x.size()
#define all(x) x.begin(),x.end()
const int N = 3e5 + 1;
typedef pair<int,int> ii;
typedef pair<int,ii> pii;
namespace BIT {
vector<int> val[N];
vector<int> tr1[N];
vector<int> tr2[N];
vector<int> tr3[N];
void ini() {
for(int i = 1 ; i < N ; ++i) {
sort(all(val[i]));
val[i].resize(unique(all(val[i])) - val[i].begin());
tr1[i].resize(sz(val[i]) + 1);
tr2[i].resize(sz(val[i]) + 1);
tr3[i].resize(sz(val[i]) + 1);
}
}
void add(int x,int y) {
for(; x > 0 ; x -= x & -x)
val[x].push_back(y);
}
void upd(int x,int y,int v) { //v < 0 -> turn off, v > 0 -> turn on
for(; x > 0 ; x -= x & -x) {
int p = lower_bound(all(val[x]),y) - val[x].begin() + 1;
for(; p > 0 ; p -= p & -p) {
tr1[x][p] += v;
if (v < 0) tr2[x][p] = max(tr2[x][p],-v);
if (v > 0) tr3[x][p] = max(tr3[x][p], v);
}
}
}
int get(int x,int y,int i) {
int ans = 0;
int lef = 0; //latest time interval [x,y] CANNOT be covered + 1
int rig = 0; //latest time interval [x,y] CAN be covered + 1
for(; x < N ; x += x & -x) {
int p = lower_bound(all(val[x]),y) - val[x].begin() + 1;
for(; p <= val[x].size() ; p += p & -p)
ans += tr1[x][p],
lef = max(lef,tr2[x][p]),
rig = max(rig,tr3[x][p]);
}
if (rig < lef)
ans += i;
return ans;
}
};
bool on[N];
set<ii> S;
vector<pii> Q[N];
int l[N];
int r[N];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
int q; cin >> q; ++q;
S.insert({-1,-1});
for(int i = 1 ; i <= n ; ++i) {
char c; cin >> c;
if (c == '1') {
ii it = (*--S.end());
if (it.Y == i - 1)
S.erase(it);
else it.X = i;
S.insert({it.X,i});
on[i] = 1;
}
}
S.insert({n + 2,n + 2});
for(ii e : S) if (1 <= e.X && e.Y <= n)
Q[1].pb(pii(1,e));
string t;
for(int i = 2 ; i <= q ; ++i) {
int x, y; cin >> t >> x;
if (t == "query") {
cin >> y;
l[i] = n - x + 1;
r[i] = y - 1;
continue;
}
if (on[x]) {
ii it = (*--S.upper_bound({x,x}));
if (it.X < x) S.insert({it.X,x - 1}), Q[i].pb(pii(1,{it.X,x - 1}));
if (it.Y > x) S.insert({x + 1,it.Y}), Q[i].pb(pii(1,{x + 1,it.Y}));
S.erase(it); Q[i].pb(pii(0,it));
}
if(!on[x]) {
auto L = S.upper_bound({x,x});
auto R = L--;
int l = x;
int r = x;
if ((*R).X == x + 1) {
r = (*R).Y;
S.erase(R);
Q[i].pb(pii(0,*R));
}
if ((*L).Y == x - 1) {
l = (*L).X;
S.erase(L);
Q[i].pb(pii(0,*L));
}
S.insert({l,r});
Q[i].pb(pii(1,{l,r}));
}
on[x] ^= 1;
}
for(int i = 1 ; i <= q ; ++i)
for(pii t : Q[i])
BIT::add(n - t.Y.X + 1,t.Y.Y);
BIT::ini(); Q[1].pb(pii(1,{n + 1,0}));
for(int i = 1 ; i <= q ; ++i) {
if (Q[i].empty()) cout << BIT::get(l[i],r[i],i) << "\n";
for(pii t : Q[i]) {
int x = -t.Y.X + n + 1;
int y = t.Y.Y;
if (t.X) BIT::upd(x,y,-i);
if(!t.X) BIT::upd(x,y, i);
}
}
}
Compilation message
street_lamps.cpp: In function 'int BIT::get(int, int, int)':
street_lamps.cpp:52:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; p <= val[x].size() ; p += p & -p)
~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
105 ms |
63864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
81 ms |
72228 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
106 ms |
63960 KB |
Output is correct |
| 2 |
Incorrect |
106 ms |
63888 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
63792 KB |
Output is correct |
| 2 |
Incorrect |
104 ms |
63864 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
105 ms |
63864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
