#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define sz size
const int mxN = 3e5+1;
int n;
bool vals[mxN];
vector<pii> ranges[mxN];
vector<int> indexs[mxN];
int cnt = 0;
int lazsum[4*(20*mxN)+1];
void sumupd(int tl, int tr, int v, int l = 0, int r = cnt-1, int idx = 0){
if (tl > tr) return;
if (l > tr || r < tl) return;
if (l >= tl && r <= tr){
lazsum[idx] += v;
return;
}
int m = (l+r)/2;
sumupd(tl,tr,v,l,m,2*idx+1);
sumupd(tl,tr,v,m+1,r,2*idx+2);
}
int sumquery(int t, int l = 0, int r = cnt-1, int idx = 0){
if (l > t || r < t){
return 0;
}
if (l == r) return lazsum[idx];
int m = (l+r)/2;
return sumquery(t,l,m,2*idx+1) + sumquery(t,m+1,r,2*idx+2) + lazsum[idx];
}
//containing ordered queries in a spec. range
vector<pii> all[4*mxN+1];
int sidx[4*mxN+1];
void build(int l = 0, int r = n-1, int idx = 0){
if (l == r){
sidx[idx] = cnt;
for (pii i : ranges[l]){
all[idx].pb(i);
indexs[i.s].pb(cnt);
cnt++;
}
return;
}
int m = (l+r)/2;
build(l,m,2*idx+1);
build(m+1,r,2*idx+2);
sidx[idx] = cnt;
int cidx = 0;
while (cidx < all[2*idx+2].sz() && all[2*idx+2][cidx].f <= r){
cidx++;
}
for (pii i : all[2*idx+1]){
if (i.f <= r) continue;
while (cidx < all[2*idx+2].sz() && all[2*idx+2][cidx].f < i.f){
all[idx].pb(all[2*idx+2][cidx]);
indexs[all[2*idx+2][cidx].s].pb(cnt);
cnt++;
cidx++;
}
all[idx].pb(i);
indexs[i.s].pb(cnt);
cnt++;
}
while (cidx < all[2*idx+2].sz()){
all[idx].pb(all[2*idx+2][cidx]);
indexs[all[2*idx+2][cidx].s].pb(cnt);
cnt++;
cidx++;
}
/* cout << l << "-" << r << " " << idx << " : ";
for (pii temp : all[idx]) cout << temp.f << ',' << temp.s << " ";
cout << '\n';*/
}
void qupd(int tl, int tr, int t, int v, int l = 0, int r = n-1, int idx = 0){
if (l > tr || r < tl) return;
if (l >= tl && r <= tr){
pii temp = {tr,mxN+1};
int fidx = lower_bound(all[idx].begin(),all[idx].end(),temp) - all[idx].begin();
temp = {t,mxN+1};
int lidx = lower_bound(all[idx].begin(),all[idx].end(),temp) - all[idx].begin();
sumupd(sidx[idx]+fidx,sidx[idx]+lidx-1,v);
return;
}
int m = (l+r)/2;
qupd(tl,tr,t,v,l,m,2*idx+1);
qupd(tl,tr,t,v,m+1,r,2*idx+2);
}
// all for fiding the bounds of a connected range
int laz[4*mxN+1][2];
void pdown(int idx, int w){
if (laz[idx][w] != -1){
laz[2*idx+1][w] = laz[idx][w];
laz[2*idx+2][w] = laz[idx][w];
}
laz[idx][w] = -1;
}
int query(int t, int w, int l = 0, int r = n-1, int idx = 0){
if (l > t || r < t) return -1;
if (l == r) return laz[idx][w];
pdown(idx,w);
int m = (l+r)/2;
int r1 = query(t,w,l,m,2*idx+1);
int r2 = query(t,w,m+1,r,2*idx+2);
if (r1 == -1) return r2;
return r1;
}
void bupd(int tl, int tr, int v, int w, int l = 0, int r = n-1, int idx = 0){
if (l > tr || r < tl) return;
if (l >= tl && r <= tr){
laz[idx][w] = v;
return;
}
pdown(idx,w);
int m = (l+r)/2;
bupd(tl,tr,v,w,l,m,2*idx+1);
bupd(tl,tr,v,w,m+1,r,2*idx+2);
}
void upd(int t, int v, int l = 0, int r = n-1, int idx = 0){
if (l > t || r < t) return;
if (l == r){
// cout << t << " - " << v << ' ';
if (vals[l]){
int lidx = query(l,0);
int ridx = query(l,1);
// cout << lidx << " " << ridx;
qupd(lidx,l,ridx,v);
vals[l] = false;
bupd(l+1,ridx,l+1,0);
bupd(lidx,l,l,1);
} else {
int lidx = query(l,0);
int ridx = query(l+1,1);
// cout << lidx << " " << ridx;
qupd(lidx,l,ridx,-1*v);
vals[l] = true;
bupd(l+1,ridx,lidx,0);
bupd(lidx,l,ridx,1);
}
// cout << '\n';
return;
}
int m = (l+r)/2;
upd(t,v,l,m,2*idx+1);
upd(t,v,m+1,r,2*idx+2);
}
int main()
{
memset(lazsum,0,sizeof(lazsum));
memset(sidx,0,sizeof(sidx));
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int q;
cin >> n >> q;
n++;
string s1;
cin >> s1;
for (int i =0; i < 4*mxN+1; i++) for (int j =0; j < 2; j++) laz[i][j] = -1;
for (int i =0; i < n; i++){
bupd(i,i,i,0);
bupd(i,i,i,1);
}
vector<pii> qu(q);
int curr = 0;
string s2;
for (int i =0; i <q; i++){
cin >> s2;
if (s2 == "toggle"){
cin >> qu[i].f;
qu[i].f -= 1;
qu[i].s = -1;
} else {
cin >> qu[i].f >> qu[i].s;
qu[i].f -= 1;
qu[i].s -= 1;
ranges[qu[i].f].pb({qu[i].s,curr});
curr++;
}
}
build();
/* cout << '\n';
for (int i =0; i < curr; i++){
cout << i << ": ";
for (int j : indexs[i]) cout << j << " ";
cout << '\n';
}
cout << '\n';*/
for (int i =0; i < n-1; i++){
vals[i] = false;
if (s1[i] == '1'){
upd(i,0);
}
}
/* for (int i =0; i < n; i++){
cout << query(i,0) << "-" << query(i,1) << " ";
}
cout << '\n';
*/
curr = 0;
int res;
for (int i = 0; i < q; i++){
if (qu[i].s == -1){
upd(qu[i].f,i+1);
/* for (int j =0; j< n; j++){
cout << query(j,0) << "-" << query(j,1) << " ";
}
cout << '\n';
*/
} else {
res = 0;
for (int j : indexs[curr]){
res += sumquery(j);
}
// cout << qu[i].s << " " << qu[i].f << ' ' << query(qu[i].s,1) << "\n";
if (query(qu[i].s,0) <= qu[i].f) res += i+1;
cout << res << '\n';
curr++;
}
}
return 0;
}
Compilation message
street_lamps.cpp: In function 'void build(int, int, int)':
street_lamps.cpp:59:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | while (cidx < all[2*idx+2].sz() && all[2*idx+2][cidx].f <= r){
| ~~~~~^~~~~~~~~~~~~~~~~~~
street_lamps.cpp:64:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | while (cidx < all[2*idx+2].sz() && all[2*idx+2][cidx].f < i.f){
| ~~~~~^~~~~~~~~~~~~~~~~~~
street_lamps.cpp:74:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | while (cidx < all[2*idx+2].sz()){
| ~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
150808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
274 ms |
166480 KB |
Output is correct |
| 2 |
Correct |
297 ms |
166996 KB |
Output is correct |
| 3 |
Correct |
351 ms |
167840 KB |
Output is correct |
| 4 |
Correct |
724 ms |
175488 KB |
Output is correct |
| 5 |
Correct |
769 ms |
178668 KB |
Output is correct |
| 6 |
Correct |
710 ms |
172444 KB |
Output is correct |
| 7 |
Correct |
586 ms |
188720 KB |
Output is correct |
| 8 |
Correct |
853 ms |
190328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
150608 KB |
Output is correct |
| 2 |
Incorrect |
45 ms |
150832 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
150868 KB |
Output is correct |
| 2 |
Incorrect |
38 ms |
150868 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
150808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
