/* 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 = 1e5+10, K = 52, MX = 30;
struct Node{
int X, Y, sz = 0, val = 0, sum = 0, sum2 = 0;
Node *L, *R;
Node(){}
Node(int key, int val) : X(key), Y(rand()), L(nullptr), R(nullptr), sz(key), val(val), sum(key * val), sum2(val) {}
// Node(int key, int pr) : X(key), Y(pr), L(nullptr), R(nullptr) {}
};
typedef Node* Nodep;
void upd_sz(Nodep v){
if(v){
v->sz = v->X;
if(v->L) v->sz = min(v->L->sz, v->sz);
if(v->R) v->sz = min(v->R->sz, v->sz);
v->sum = v->val * v->X;
// cout << v->X << ' ' << v->sum << ' ' << v->val << "ff\n";
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;
}
}
int get(Nodep x){
if(!x) return MOD;
return x->sz;
}
pair<Nodep, Nodep> split(Nodep v, int key){
if(!v){
return {v, v};
}
else if(get(v->R) <= key || v->X <= key){
// cout << key << "wtf\n";
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};
}
}
Nodep merge(Nodep l, Nodep r){
if(!l || !r){
return l ? l : r;
}else if(l->Y > r->Y){
auto p = merge(l->R, r);
l->R = p;
upd_sz(l);
return l;
}else{
auto p = merge(l, r->L);
r->L = p;
upd_sz(r);
return r;
}
}
Nodep insert(Nodep v, Nodep it){
auto a = split(v, it->X);
return merge(merge(a.first, it), a.second);
}
int n, q, ans[N];
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){
Nodep A = new Node(t1, 1);
Nodep B = new Node(t2, -1);
T[k] = merge(T[k], A);
T[k] = merge(T[k], B);
// 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){
int val = 0;
auto halves = split(T[k], tm);
val += halves.ff->sum2 * tm - halves.ff->sum;
// cout << tm << ' ' << l << ' ' << r << ' ' << halves.ff->sum2 << ' ' << halves.ff->sum << ' ' << val << '\n';
T[k] = merge(halves.ff, halves.ss);
return val;
}
int m = l+r>>1;
if(p <= m){
int val = 0;
auto halves = split(T[k<<1|1], tm);
val += halves.ff->sum2 * tm - halves.ff->sum;
// cout << halves.ff->X << ' ' << tm << ' ' << l << ' ' << r << ' ' << halves.ff->sum2 << ' ' << halves.ff->sum << ' ' << val << '\n';
T[k<<1|1] = merge(halves.ff, halves.ss);
return get(l, m, p, k<<1, tm) + val;
}
return get(m+1, r, p, k<<1|1, tm);
}
vector<array<int, 3>> Q[N];
void solve(){
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 f: S){
// cout << f[0] << ' ' << f[1] << ' ' << f[2] << '\n';
// }
// en;
// cout << endl;
}
for(auto p: S){
R.pb({p[0], p[1], p[2], q});
}
sort(all(R));
// for(auto f: R){
// cout << f[0] << ' ' << f[1] << ' ' << f[2] << ' ' << f[3] << '\n';
// }
// en;en;
build(1, n + 1, 1);
int p = 0;
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;
}
}
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:13: warning: 'Node::R' will be initialized after [-Wreorder]
17 | Node *L, *R;
| ^
street_lamps.cpp:16:13: warning: 'int Node::sz' [-Wreorder]
16 | int X, Y, sz = 0, val = 0, sum = 0, sum2 = 0;
| ^~
street_lamps.cpp:19:3: warning: when initialized here [-Wreorder]
19 | Node(int key, int val) : X(key), Y(rand()), L(nullptr), R(nullptr), sz(key), val(val), sum(key * val), sum2(val) {}
| ^~~~
street_lamps.cpp: In function 'void build(int, int, int)':
street_lamps.cpp:94:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
94 | int m = l+r>>1;
| ~^~
street_lamps.cpp: In function 'void upd(int, int, int, int, int, int)':
street_lamps.cpp:109:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
109 | int m = l+r>>1;
| ~^~
street_lamps.cpp: In function 'int get(int, int, int, int, long long int)':
street_lamps.cpp:124:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
124 | int m = l+r>>1;
| ~^~
street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:208: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]
208 | while(p < R.size() && R[p][0] == l){
| ~~^~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:231:15: warning: unused variable 'aa' [-Wunused-variable]
231 | int tt = 1, aa;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
49752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
528 ms |
220652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
52060 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
51332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
50524 KB |
Output is correct |
| 2 |
Correct |
14 ms |
50780 KB |
Output is correct |
| 3 |
Incorrect |
11 ms |
51424 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
49752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
