#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
#include <random>
#include <chrono>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ld long double
const ll maxn = 1e6 + 1, maxm = 80;
const ll mod = 1e9 + 7, inf = 1e9, blck = 500;
const ld eps = 1e-9;
int n, q;
string s, type;
set<int> setik;
ll rng(){
return ((rand() << 15) + rand());
}
struct tnode{
ll pos, sum, y, prior;
tnode *l, *r;
tnode(int x, int z){
pos = x;
y = z;
sum = z;
prior = rng();
l = r = nullptr;
}
};
struct treap{
ll getsum(tnode *v){
return (v ? v->sum : 0);
}
void pull(tnode *v){
v->sum = getsum(v->l) + v->y + getsum(v->r);
}
pair<tnode*, tnode*> split(tnode* &v, int val){
if (v == nullptr)
return {v, v};
if (v->pos < val){
pair<tnode*, tnode*> splitted = split(v->r, val);
v->r = splitted.f;
pull(v);
return mp(v, splitted.s);
}
else{
pair<tnode*, tnode*> splitted = split(v->l, val);
v->l = splitted.f;
pull(v);
return mp(splitted.f, v);
}
}
tnode *merge(tnode *l, tnode *r){
if (l == nullptr || r == nullptr){
return (l ? l : r);
}
if (l->prior > r->prior){
l->r = merge(l->r, r);
pull(l);
return l;
}
else{
r->l = merge(l, r->l);
pull(r);
return r;
}
}
int is(tnode* &v, int x, ll z){
if (v == nullptr)
return 0;
if (v->pos == x){
v->sum += z;
v->y += z;
return 1;
}
int ok = 0;
if (v->pos < x){
ok = is(v->r, x, z);
}
else{
ok = is(v->l, x, z);
}
pull(v);
return ok;
}
void insval(tnode* &v, int x, int z){
if (is(v, x, z)){
return;
}
pair<tnode*, tnode*> split1 = split(v, x);
tnode* cur = new tnode(x, z);
v = merge(merge(split1.f, cur), split1.s);
return;
}
int get(int r, tnode* &v){
if (v == nullptr)
return 0;
if (v->pos <= r){
return getsum(v->l) + v->y + get(r, v->r);
}
else{
return get(r, v->l);
}
}
} tree;
struct seg_tree{
tnode *t[maxn << 2];
void upd(int l, int r, int l2, int r2, int add, int v = 1, int tl = 1, int tr = n){
if (l > tr || r < tl)
return;
if (l <= tl && tr <= r){
tree.insval(t[v], l2, add);
tree.insval(t[v], r2, -add);
return;
}
int tm = (tl + tr) / 2;
upd(l, r, l2, r2, add, v + v, tl, tm);
upd(l, r, l2, r2, add, v + v + 1, tm + 1, tr);
}
int get(int l, int r, int v = 1, int tl = 1, int tr = n){
if (l > tr || r < tl)
return 0;
if (tl == tr){
return tree.get(r, t[v]);
}
int tm = (tl + tr) / 2;
int add = tree.get(r, t[v]);
if (l <= tm){
add += get(l, r, v + v, tl, tm);
}
else{
add += get(l, r, v + v + 1, tm + 1, tr);
}
return add;
}
} tree2;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
cin >> s;
s = '#'+ s;
setik.insert(0);
setik.insert(n + 1);
for (int i = 1; i <= n; ++i){
if (s[i] == '0'){
setik.insert(i);
}
}
for (int x, l, r, i = 1; i <= q; ++i){
cin >> type;
if (type == "toggle"){
int x;
cin >> x;
if (s[x] == '0'){
setik.erase(x);
auto it = setik.upper_bound(x);
r = *it;
l = *(--it) + 1;
// cout << l << " " << x << " " << x << " " << r << '\n';
tree2.upd(l, x, x, r, -i);
s[x] = '1';
}
else{
auto it = setik.upper_bound(x);
r = *it;
l = *(--it) + 1;
// cout << l << " " << r << '\n';
setik.insert(x);
tree2.upd(l, x, x, r, i);
s[x] = '0';
}
}
else{
int l, r;
cin >> l >> r;
int add = 0;
auto it = setik.lower_bound(l);
if (*it > r - 1){
add = 1;
}
// cout << tree2.get(l, r - 1) << '\n';
cout << tree2.get(l, r - 1) + add * i << '\n';
}
}
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:180:14: warning: unused variable 'x' [-Wunused-variable]
180 | for (int x, l, r, i = 1; i <= q; ++i){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5047 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
472 KB |
Output is correct |
| 3 |
Correct |
2 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
584 ms |
71956 KB |
Output is correct |
| 6 |
Correct |
491 ms |
61788 KB |
Output is correct |
| 7 |
Correct |
419 ms |
48728 KB |
Output is correct |
| 8 |
Correct |
134 ms |
8604 KB |
Output is correct |
| 9 |
Correct |
70 ms |
3924 KB |
Output is correct |
| 10 |
Correct |
77 ms |
4292 KB |
Output is correct |
| 11 |
Correct |
74 ms |
4500 KB |
Output is correct |
| 12 |
Correct |
339 ms |
21472 KB |
Output is correct |
| 13 |
Correct |
128 ms |
8624 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
265 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
