/* 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;
#define upd_sz(_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;}}
inline pair<Nodep, Nodep> split(Nodep v, int key){
if(!v){
return {v, v};
}
else if(v->X <= key){
auto p = split(v->R, key);
v->R = p.first;
upd_sz(v);
return {v, p.second};
}else{
auto p = split(v->L, key);
v->L = p.second;
upd_sz(v);
return {p.first, v};
}
}
int query(Nodep p, int key){
int val = 0;
while(p){
if(p->X <= key){
val += p->val * key - p->val * p->X;
if(p->L) val += p->L->sum2 * key - p->L->sum;
p = p->R;
}else{
p = p->L;
}
}
return val;
}
inline 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;
}
inline void dfs(Nodep t){
if(t->L) dfs(t->L);
if(t->R) dfs(t->R);
free(t);
}
inline 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];
inline 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);
}
inline 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);
}
inline int get(int l, int r, int p, int k, int 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);
}
inline 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];
inline void solve(){
// cout << sizeof(Node) << '\n';
cin >> n >> q >> s;
vector<int> val;
vector<array<int, 4>> R, QQ;
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;
QQ.pb({a, b, i + 1, qq});
qq++;
}
}
for(auto p: S){
R.pb({p[0], p[1], p[2], q});
val.pb(p[0]);
val.pb(p[1]);
}
sort(all(val));
for(auto &p: R){
p[0] = lower_bound(all(val), p[0]) - val.begin() + 1;
p[1] = lower_bound(all(val), p[1]) - val.begin() + 1;
}
for(auto &p :QQ){
p[0] = lower_bound(all(val), p[0]) - val.begin() + 1;
p[1] = lower_bound(all(val), p[1]) - val.begin() + 1;
Q[p[0]].pb({p[1], p[2], p[3]});
}
S.clear();
sort(all(R));
n = val.size();
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;
}
// if(l <= n/2)
F(1, n+1, l, 1);
}
for(int i = 0; i < qq; ++i) cout << ans[i] << '\n';
}
int32_t 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:101:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
101 | int m = l+r>>1;
| ~^~
street_lamps.cpp: In function 'void upd(int, int, int, int, int, int)':
street_lamps.cpp:120:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
120 | int m = l+r>>1;
| ~^~
street_lamps.cpp: In function 'int get(int, int, int, int, int)':
street_lamps.cpp:130:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
130 | int m = l+r>>1;
| ~^~
street_lamps.cpp: In function 'void F(int, int, int, int)':
street_lamps.cpp:143:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
143 | int m = l+r>>1;
| ~^~
street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:232: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]
232 | while(p < R.size() && R[p][0] == l){
| ~~^~~~~~~~~~
street_lamps.cpp: In function 'int32_t main()':
street_lamps.cpp:259:17: warning: unused variable 'aa' [-Wunused-variable]
259 | int tt = 1, aa;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1180 ms |
50528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
11100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10844 KB |
Output is correct |
| 2 |
Correct |
5 ms |
11088 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
11148 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
