#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 NN = 2e6+100, M = 3e5+10, K = 52, MX = 30;
#define upd_sz(_v) {if(_v){_v->sum = _v->val * _v->key;_v->sum2 = _v->val;if(_v->left) _v->sum += _v->left->sum;if(_v->right) _v->sum += _v->right->sum;if(_v->left) _v->sum2 += _v->left->sum2;if(_v->right) _v->sum2 += _v->right->sum2;}}
// An AVL tree node
class Node
{
public:
int key;
Node *left;
Node *right;
int height, sum, sum2, val;
};
// A utility function to get the
// height of the tree
int height(Node *N)
{
if (N == NULL)
return 0;
return N->height;
}
/* Helper function that allocates a
new node with the given key and
NULL left and right pointers. */
Node* newNode(int key, int val)
{
Node* node = new Node();
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // new node is initially
node->val = val;
node->sum = key * val;
node->sum2 = val;
// added at leaf
return(node);
}
// A utility function to right
// rotate subtree rooted with y
// See the diagram given above.
Node *rightRotate(Node *y)
{
Node *x = y->left;
Node *T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->height = max(height(y->left),
height(y->right)) + 1;
x->height = max(height(x->left),
height(x->right)) + 1;
upd_sz(x);
upd_sz(y);
upd_sz(x);
upd_sz(y);
// Return new root
return x;
}
// A utility function to left
// rotate subtree rooted with x
// See the diagram given above.
Node *leftRotate(Node *x)
{
Node *y = x->right;
Node *T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = max(height(x->left),
height(x->right)) + 1;
y->height = max(height(y->left),
height(y->right)) + 1;
upd_sz(y);
upd_sz(x);
upd_sz(y);
upd_sz(x);
// Return new root
return y;
}
// Get Balance factor of node N
int getBalance(Node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
// Recursive function to insert a key
// in the subtree rooted with node and
// returns the new root of the subtree.
Node* insert(Node* node, int key, int val)
{
/* 1. Perform the normal BST insertion */
if (node == NULL)
return(newNode(key, val));
if (key <= node->key)
node->left = insert(node->left, key, val);
else if (key > node->key)
node->right = insert(node->right, key, val);
/* 2. Update height of this ancestor node */
node->height = 1 + max(height(node->left),
height(node->right));
/* 3. Get the balance factor of this ancestor
node to check whether this node became
unbalanced */
int balance = getBalance(node);
// If this node becomes unbalanced, then
// there are 4 cases
// Left Left Case
if (balance > 1 && key < node->left->key)
return rightRotate(node);
// Right Right Case
if (balance < -1 && key > node->right->key)
return leftRotate(node);
// Left Right Case
if (balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && key < node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
upd_sz(node);
/* return the (unchanged) node pointer */
return node;
}
typedef Node* Nodep;
int query(Nodep p, int key){
int val = 0;
while(p){
if(p->key <= key){
val += p->val * key - p->val * p->key;
if(p->left) val += p->left->sum2 * key - p->left->sum;
p = p->right;
}else{
p = p->left;
}
}
return val;
}
inline void dfs(Nodep t){
// if(t->left) dfs(t->left);
// if(t->right) dfs(t->right);
// free(t);
}
int n, q, ans[M];
string s;
Nodep T[NN];
inline void build(int l, int r, int k){
if(l == r){
T[k] = NULL;
return;
}
int m = l+r>>1;
build(l, m, k<<1);
build(m+1, r, k<<1|1);
T[k] = NULL;
}
inline void upd(int l, int r, int p, int k, int t1, int t2){
if(!(l == 1 && r == n)){
// Nodep A = new Node(t1, 1);
// Nodep B = new Node(t2, -1);
T[k] = insert(T[k], t1, 1);
T[k] = insert(T[k], t2, -1);
}
// 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});
}
for(auto p: R) val.pb(p[1]);
sort(all(val));
val.erase(unique(all(val)), val.end());
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() + 1;
build(1, n, 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; ++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, 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, r, 1, tm);
// cout << ans[idx] << ' ';
// en;en;
}
// if(l <= n/2)
F(1, n, 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 function 'void build(int, int, int)':
street_lamps.cpp:199:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
199 | int m = l+r>>1;
| ~^~
street_lamps.cpp: In function 'void upd(int, int, int, int, int, int)':
street_lamps.cpp:218:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
218 | int m = l+r>>1;
| ~^~
street_lamps.cpp: In function 'int get(int, int, int, int, int)':
street_lamps.cpp:228:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
228 | int m = l+r>>1;
| ~^~
street_lamps.cpp: In function 'void F(int, int, int, int)':
street_lamps.cpp:241:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
241 | int m = l+r>>1;
| ~^~
street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:329:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
329 | while(p < R.size() && R[p][0] == l){
| ~~^~~~~~~~~~
street_lamps.cpp: In function 'int32_t main()':
street_lamps.cpp:356:17: warning: unused variable 'aa' [-Wunused-variable]
356 | int tt = 1, aa;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10680 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 3 |
Runtime error |
10 ms |
21596 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
177 ms |
76656 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
21768 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
21904 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10680 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 3 |
Runtime error |
10 ms |
21596 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
