#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
//#define int long long int
using namespace std;
#define rand() (rand() * rand() + rand() + 1)
vector<int> ans(300005, 0);
struct Node{
int left, right;
int key, prior;
int id, lazy;
Node(){
left = right = key = prior = id = lazy = 0;
}
bool operator<(Node& b){
return key < b.key || (key == b.key && id < b.id);
}
} node[7000000];
int new_node(int k = 0, int i = 0){
static int ind = 1; assert(ind < 7000000);
node[ind].key = k;
node[ind].id = i;
node[ind].prior = rand();
return ind++;
}
struct Treap{
int root = 0;
void push(int j){
if(!j) return;
int l = node[j].left;
int r = node[j].right;
int& z = node[j].lazy;
ans[node[j].id] += z;
if(l) node[l].lazy += z;
if(r) node[r].lazy += z;
z = 0;
}
void split(int j, Node& v, int& l, int& r){
push(j);
if(!j) l = r = 0;
else if(node[j] < v) split(node[j].right, v, node[j].right, r), l = j;
else split(node[j].left, v, l, node[j].left), r = j;
}
void merge(int& j, int l, int r){
push(l), push(r);
if(!l || !r) j = max(l, r);
else if(node[l].prior > node[r].prior) merge(node[l].right, node[l].right, r), j = l;
else merge(node[r].left, l, node[r].left), j = r;
}
void insert(int& j, int i){
push(j);
if(!j) j = i;
else if(node[i].prior < node[j].prior){
if(node[i] < node[j]) insert(node[j].left, i);
else insert(node[j].right, i);
}
else split(j, node[i], node[i].left, node[i].right), j = i;
}
void add(int k, int id){
insert(root, new_node(k, id));
}
void update(int y1, int y2, int v){
int a, b, c;
Node temp1, temp2;
temp1.key = y1;
temp1.id = -1e9;
temp2.key = y2;
temp2.id = 1e9;
split(root, temp1, a, b);
split(b, temp2, b, c);
node[b].lazy += v;
merge(root, a, b);
merge(root, root, c);
}
int find(int j, Node& c){
push(j);
if(node[j].id == c.id)return j;
if(c < node[j]) return find(node[j].left, c);
else return find(node[j].right, c);
}
};
const int S = 524288;
const int size = S * 2;
Treap seg[size];
void update(int x1, int x2, int y1, int y2, int v, int j = 1, int l = 0, int r = S - 1){
if(r < x1 || x2 < l) return;
if(x1 <= l && r <= x2){
seg[j].update(y1, y2, v);
}
else{
update(x1,x2,y1,y2,v,j*2,l,(l+r)/2);
update(x1,x2,y1,y2,v,j*2+1,(l+r)/2+1,r);
}
}
void add(int x, int y, int id){
int j = x + S;
while(j != 0){
seg[j].add(y, id);
j /= 2;
}
}
void find(int x, int y, int id){
int j = x + S;
Node c;
c.key = y;
c.id = id;
while(j != 0){
seg[j].find(seg[j].root, c);
j /= 2;
}
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
srand(time(NULL));
int n, q;
cin >> n >> q;
string s; cin >> s;
vector<bool> open(n, false);
map<int, int> range;
for(int i = 1; i <= n; i++){
if(s[i - 1] == '1') open[i] = true;
}
vector<string>K(q+1);
vector<int> L(q+1), R(q+1);
for(int i = 1; i <= q; i++){
cin >> K[i];
if(K[i] == "toggle") cin >> L[i];
else cin >> L[i] >> R[i], add(L[i], --R[i], i);
}
int last = 0;
for(int i = 1; i <= n; i++){
if(open[i]){
if(!last) last = i;
}
else{
if(last){
range[last] = i - 1;
last = 0;
}
}
}
if(last) range[last] = n;
for(int i = 1; i <= q; i++){
if(K[i] == "toggle"){
int x = L[i];
if(open[x]){
auto itr = --range.upper_bound(x);
int l = itr->first, r = itr->second;
update(l, x, x, r, i);
range.erase(itr);
if(x != l){
range[l] = x - 1;
}
if(x != r){
range[x + 1] = r;
}
}
else{
auto itr = range.lower_bound(x);
int l = x;
int r = x;
if(itr != range.end() && itr->first == x + 1){
r = itr->second;
range.erase(itr);
}
auto itl = range.upper_bound(x);
if(itl != range.begin()){
itl--;
if(itl->second + 1 == x){
l = itl->first;
range.erase(itl);
}
}
range[l] = r;
update(l, x, x, r, -i);
}
open[x] = open[x] ^ 1;
}
else{
auto itr = range.upper_bound(L[i]);
int add = 0;
if(itr != range.begin() && (--itr)->second >= R[i]) add = i;
find(L[i], R[i], i);
cout << ans[i] + add << '\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
165880 KB |
Output is correct |
| 2 |
Correct |
89 ms |
165880 KB |
Output is correct |
| 3 |
Correct |
97 ms |
165880 KB |
Output is correct |
| 4 |
Correct |
88 ms |
165880 KB |
Output is correct |
| 5 |
Correct |
94 ms |
165880 KB |
Output is correct |
| 6 |
Correct |
90 ms |
165880 KB |
Output is correct |
| 7 |
Correct |
91 ms |
166008 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5078 ms |
182008 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
93 ms |
166008 KB |
Output is correct |
| 2 |
Correct |
93 ms |
166008 KB |
Output is correct |
| 3 |
Correct |
93 ms |
166008 KB |
Output is correct |
| 4 |
Correct |
97 ms |
166008 KB |
Output is correct |
| 5 |
Correct |
474 ms |
188172 KB |
Output is correct |
| 6 |
Correct |
3060 ms |
189196 KB |
Output is correct |
| 7 |
Execution timed out |
5018 ms |
189460 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
166008 KB |
Output is correct |
| 2 |
Correct |
94 ms |
166008 KB |
Output is correct |
| 3 |
Correct |
97 ms |
166008 KB |
Output is correct |
| 4 |
Correct |
91 ms |
165880 KB |
Output is correct |
| 5 |
Execution timed out |
5067 ms |
186124 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
165880 KB |
Output is correct |
| 2 |
Correct |
89 ms |
165880 KB |
Output is correct |
| 3 |
Correct |
97 ms |
165880 KB |
Output is correct |
| 4 |
Correct |
88 ms |
165880 KB |
Output is correct |
| 5 |
Correct |
94 ms |
165880 KB |
Output is correct |
| 6 |
Correct |
90 ms |
165880 KB |
Output is correct |
| 7 |
Correct |
91 ms |
166008 KB |
Output is correct |
| 8 |
Execution timed out |
5078 ms |
182008 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
