/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
const int N = 2e6+100, M = 3e5+10, K = 52, MX = 30;
struct Node{
int X, sum = 0, sum2 = 0;
int Y, val;
Node *L, *R;
Node(){}
Node(int key, int val) : X(key), Y(rand()), L(nullptr), R(nullptr), val(val), sum(key * val), sum2(val) {}
};
typedef Node* Nodep;
inline void upd_sz(Nodep _v) {if(_v){_v->sum = _v->val * _v->X;_v->sum2 = _v->val;if(_v->L) _v->sum += _v->L->sum;if(_v->R) _v->sum += _v->R->sum;if(_v->L) _v->sum2 += _v->L->sum2;if(_v->R) _v->sum2 += _v->R->sum2;}}
Nodep*lefties[50],*righties[50];
pair<Nodep, Nodep> split(Nodep v, int key){
Nodep left=0,right=0;
lefties[0]=&left,righties[0]=&right;
int ind1=0,ind2=0;
while(v){
if(v->X <= key){
*lefties[ind1]=v;
lefties[ind1+1]=&v->R;
ind1++;
v=v->R;
}else{
*righties[ind2]=v;
righties[ind2+1]=&v->L;
ind2++;
v=v->L;
}
}
ind1--,ind2--;
while(0<=ind1){
upd_sz((*lefties[ind1]));
ind1--;
}
while(0<=ind2){
upd_sz((*righties[ind2]));
ind2--;
}
return pair<Nodep,Nodep>(left,right);
}
int query(Nodep p,int key){
if(!p)return 0;
if(p->X<=key){
int toret=p->val*key-p->val*p->X;
if(p->L)toret+=p->L->sum2*key-p->L->sum;
return toret+query(p->R,key);
}
return query(p->L,key);
}
Nodep insert(Nodep v, Nodep it){
if(!v) return it;
if(v->Y > it->Y){
if(v->X <= it->X) v->R = insert(v->R, it);
else v->L = insert(v->L, it);
upd_sz(v);
return v;
}else{
auto a = split(v, it->X);
it->L = a.ff;
it->R = a.ss;
upd_sz(it);
}
return it;
}
void dfs(Nodep t){
if(t->L) dfs(t->L);
if(t->R) dfs(t->R);
free(t);
}
void dfs2(Nodep t){
// if(t->L)
// cout << "go left: ";
if(t->L) dfs2(t->L);
// cout << "par: ";
// cout << t->Y << ' ';
// if(t->R)
// cout << "go right: ";
if(t->R) dfs2(t->R);
}
int n, q, ans[M];
string s;
Nodep T[N];
void build(int l, int r, int k){
if(l == r){
T[k] = new Node(0, 0);
return;
}
int m = l+r>>1;
build(l, m, k<<1);
build(m+1, r, k<<1|1);
T[k] = new Node(0, 0);
}
void upd(int l, int r, int p, int k, int t1, int t2){
if(!(l == 1 && r == n + 1)){
Nodep A = new Node(t1, 1);
Nodep B = new Node(t2, -1);
T[k] = insert(T[k], A);
T[k] = insert(T[k], B);
}
// dfs2(T[k]);en;en;
// cout << "insert:" << l << ' ' << r << ' ' << p << ' ' << t1 << ' ' << t2 << '\n';
if(l == r){
return;
}
int m = l+r>>1;
if(p <= m) upd(l, m, p, k<<1, t1, t2);
else upd(m+1, r, p, k<<1|1, t1, t2);
}
int get(int l, int r, int p, int k, ll tm){
if(l == r){
return query(T[k],tm);
}
// dfs2(T[k]);en;en;
int m = l+r>>1;
if(p <= m){
int val = query(T[k<<1|1],tm);
return get(l, m, p, k<<1, tm) + val;
}
return get(m+1, r, p, k<<1|1, tm);
}
void F(int l, int r, int p, int k){
if(l == r){
dfs(T[k]);
return;
}
int m = l+r>>1;
if(p <= m) F(l, m, p, k<<1);
else F(m+1, r, p, k<<1|1);
if(p == r) dfs(T[k]);
}
vector<array<int, 3>> Q[M];
void solve(){
// cout << sizeof(Node) << '\n';
cin >> n >> q >> s;
vector<array<int, 4>> R;
int last = 1;
s += '0';
set<array<int, 3>> S;
for(int i = 0; i <= n; ++i){
if(s[i] == '0'){
S.insert({last, i + 1, 0});
last = i + 2;
}
}
int qq = 0;
for(int i = 0; i < q; ++i){
string x; int a, b; cin >> x;
if(x == "toggle"){
cin >> a;
--a;
if(s[a] == '0'){
s[a] = '1';
++a;
auto it = S.lower_bound(array<int, 3>{a + 1, -1, -1});
assert(it != S.begin());
auto it2 = prev(it);
auto x = *it, y = *it2;
S.erase(it2);
S.erase(S.find(x));
S.insert({y[0], x[1], i + 1}); // check
R.pb({x[0], x[1], x[2], i + 1});
R.pb({y[0], y[1], y[2], i + 1});
}else{
s[a] = '0';
++a;
auto it = S.lower_bound(array<int, 3>{a + 1, -1, -1});
assert(it != S.begin());
it = prev(it);
auto x = *it;
S.erase(it);
S.insert({x[0], a, i + 1}); // check
S.insert({a + 1, x[1], i + 1}); // check
R.pb({x[0], x[1], x[2], i + 1});
}
}else{
cin >> a >> b;
Q[a].pb({b, i + 1, qq});
qq++;
}
}
for(auto p: S){
R.pb({p[0], p[1], p[2], q});
}
S.clear();
sort(all(R));
build(1, n + 1, 1);
int p = 0;
// for(auto f: R){
// cout << f[0] << ' ' << f[1] << ' ' << f[2] << ' ' << f[3] << '\n';
// }
// en;en;
for(int l = 1; l <= n + 1; ++l){
while(p < R.size() && R[p][0] == l){
// cout << R[p][0] << ' ' << R[p][1] << ' ' << R[p][2] << ' ' << R[p][3] << '\n';
int r = R[p][1], t1 = R[p][2], t2 = R[p][3];
upd(1, n+1, r, 1, t1, t2);
++p;
}
for(auto query: Q[l]){
int r = query[0], tm = query[1], idx = query[2];
// cout << l << ' ' << r << '\n';
ans[idx] = get(1, n + 1, r, 1, tm);
// cout << ans[idx] << ' ';
// en;en;
}
F(1, n+1, l, 1);
}
for(int i = 0; i < qq; ++i) cout << ans[i] << '\n';
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
Compilation message
street_lamps.cpp: In constructor 'Node::Node(int, int)':
street_lamps.cpp:17:15: warning: 'Node::R' will be initialized after [-Wreorder]
17 | Node *L, *R;
| ^
street_lamps.cpp:16:12: warning: 'int Node::val' [-Wreorder]
16 | int Y, val;
| ^~~
street_lamps.cpp:19:5: warning: when initialized here [-Wreorder]
19 | Node(int key, int val) : X(key), Y(rand()), L(nullptr), R(nullptr), val(val), sum(key * val), sum2(val) {}
| ^~~~
street_lamps.cpp:16:12: warning: 'Node::val' will be initialized after [-Wreorder]
16 | int Y, val;
| ^~~
street_lamps.cpp:15:12: warning: 'int Node::sum' [-Wreorder]
15 | int X, sum = 0, sum2 = 0;
| ^~~
street_lamps.cpp:19:5: warning: when initialized here [-Wreorder]
19 | Node(int key, int val) : X(key), Y(rand()), L(nullptr), R(nullptr), val(val), sum(key * val), sum2(val) {}
| ^~~~
street_lamps.cpp: In function 'void build(int, int, int)':
street_lamps.cpp:109:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
109 | int m = l+r>>1;
| ~^~
street_lamps.cpp: In function 'void upd(int, int, int, int, int, int)':
street_lamps.cpp:128:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
128 | int m = l+r>>1;
| ~^~
street_lamps.cpp: In function 'int get(int, int, int, int, long long int)':
street_lamps.cpp:138:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
138 | int m = l+r>>1;
| ~^~
street_lamps.cpp: In function 'void F(int, int, int, int)':
street_lamps.cpp:151:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
151 | int m = l+r>>1;
| ~^~
street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:226:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
226 | while(p < R.size() && R[p][0] == l){
| ~~^~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:252:17: warning: unused variable 'aa' [-Wunused-variable]
252 | int tt = 1, aa;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
21592 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
101 ms |
41768 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
22108 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
21988 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
21592 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
