#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define PB push_back
#define MP make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define pdd pair<ld, ld>
#define ft first
#define sd second
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
template<class T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int N = 300100;
const int M = 2 * N;
const int oo = 2e9;
const ll OO = 1e18;
const int md = 998244353;
const int PW = 233;
set<pii> st;
set<pii>::iterator ite;
vector<pii> qr, pts;
string qu, s;
int q, n;
bool state[N];
struct seg_tree{
vector<int> ys;
vector<ll> st;
seg_tree(): ys(0), st(0) {}
void update(int v, int l, int r, int y, int vl){
if (ys[l] > y) return;
if (ys[r] <= y) {
st[v] += vl;
return;
}
if (l == r) return;
int md = (l + r) >> 1;
update(v + v, l, md, y, vl);
update(v + v + 1, md + 1, r, y, vl);
}
ll get(int v, int l, int r, int y){
ll res = st[v];
if (l == r) return res;
int md = (l + r) >> 1;
if (ys[md + 1] <= y)
res += get(v + v + 1, md + 1, r, y);
else res += get(v + v, l, md, y);
return res;
}
};
seg_tree seg[4 * N];
void build(int v, int l, int r){
if (l == r){
seg[v].ys.PB(pts[l].sd);
seg[v].st.resize(2);
return;
}
int md = (l + r) >> 1;
build(v + v, l, md);
build(v + v + 1, md + 1, r);
merge(all(seg[v + v].ys), all(seg[v + v + 1].ys), back_inserter(seg[v].ys));
seg[v].st.resize(sz(seg[v].ys) * 4 + 3);
}
void update(int v, int l, int r, int min_x, int max_y, int vl){
if (pts[r].ft < min_x) return;
if (pts[l].ft >= min_x) {
seg[v].update(1, 0, sz(seg[v].ys) - 1, max_y, vl);
return;
}
if (l == r) return;
int md = (l + r) >> 1;
update(v + v, l, md, min_x, max_y, vl);
update(v + v + 1, md + 1, r, min_x, max_y, vl);
}
ll get(int v, int l, int r, int min_x, int max_y){
ll res = seg[v].get(1, 0, sz(seg[v].ys) - 1, max_y);
if (l == r) return res;
int md = (l + r) >> 1;
if (MP(min_x, max_y) <= pts[md])
res += get(v + v, l, md, min_x, max_y);
else res += get(v + v + 1, md + 1, r, min_x, max_y);
return res;
}
int main() {
#ifdef _LOCAL
// freopen("in.txt","r",stdin); // freopen("output.txt","w",stdout);
#else
// freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
#endif
cin >> n >> q >> s;
for (int i = 0; i < n; i++)
state[i] = s[i] - '0';
for (int i = 0; i < q; i++){
cin >> qu;
if (qu[0] == 'q'){
int x, y; cin >> x >> y;
x--; y--;
qr.PB(MP(x, y));
pts.PB(MP(x, y));
} else {
int x; cin >> x;
x--;
qr.PB(MP(x, -228));
}
}
sort(all(pts));
pts.resize(unique(all(pts)) - pts.begin());
build(1, 0, sz(pts) - 1);
for (int i = 0; i <= n;){
int j = i;
while (j < n && state[j])
j++;
st.insert(MP(i, j));
i = j + 1;
}
// for (pii cr : pts)
// cerr << cr.ft << " " << cr.sd << '\n';
int tim = 1;
for (pii cr : qr) {
//
// for (auto x : st)
// cerr << x.ft << " " << x.sd << '\n';
// cerr << "\n\n";
if (cr.sd == -228){
int i = cr.ft;
if (!state[i]){
ite = prev(st.upper_bound(MP(i + 1, oo)));
int lf = (*prev(ite)).ft;
int rt = (*ite).sd;
st.erase(MP(lf, i));
st.erase(MP(i + 1, rt));
st.insert(MP(lf, rt));
update(1, 0, sz(pts) - 1, lf, rt, -tim);
update(1, 0, sz(pts) - 1, lf, i, tim);
update(1, 0, sz(pts) - 1, i + 1, rt, tim);
} else {
pii segm = *(prev(st.upper_bound(MP(i + 1, -oo))));
st.erase(segm);
st.insert(MP(segm.ft, i));
st.insert(MP(i + 1, segm.sd));
update(1, 0, sz(pts) - 1, segm.ft, segm.sd, tim);
update(1, 0, sz(pts) - 1, segm.ft, i, -tim);
update(1, 0, sz(pts) - 1, i + 1, segm.sd, -tim);
}
state[i] ^= 1;
} else {
ll res = get(1, 0, sz(pts) - 1, cr.ft, cr.sd);
pii segm = *prev(st.upper_bound(MP(cr.ft, oo)));
if (segm.ft <= cr.ft && segm.sd >= cr.sd)
res += tim;
cout << res << '\n';
}
tim++;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
56704 KB |
Output is correct |
2 |
Correct |
37 ms |
56704 KB |
Output is correct |
3 |
Correct |
35 ms |
56696 KB |
Output is correct |
4 |
Correct |
35 ms |
56696 KB |
Output is correct |
5 |
Correct |
36 ms |
56696 KB |
Output is correct |
6 |
Correct |
36 ms |
56828 KB |
Output is correct |
7 |
Correct |
43 ms |
56696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
257 ms |
63324 KB |
Output is correct |
2 |
Correct |
308 ms |
66772 KB |
Output is correct |
3 |
Correct |
498 ms |
68568 KB |
Output is correct |
4 |
Correct |
1484 ms |
158204 KB |
Output is correct |
5 |
Correct |
1575 ms |
174080 KB |
Output is correct |
6 |
Correct |
1254 ms |
144120 KB |
Output is correct |
7 |
Correct |
2132 ms |
225508 KB |
Output is correct |
8 |
Correct |
1705 ms |
213736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
56832 KB |
Output is correct |
2 |
Correct |
38 ms |
56696 KB |
Output is correct |
3 |
Correct |
38 ms |
57080 KB |
Output is correct |
4 |
Correct |
37 ms |
57216 KB |
Output is correct |
5 |
Correct |
680 ms |
79608 KB |
Output is correct |
6 |
Correct |
1266 ms |
139880 KB |
Output is correct |
7 |
Correct |
1780 ms |
207572 KB |
Output is correct |
8 |
Correct |
2231 ms |
308104 KB |
Output is correct |
9 |
Correct |
275 ms |
67160 KB |
Output is correct |
10 |
Correct |
308 ms |
67264 KB |
Output is correct |
11 |
Correct |
334 ms |
70344 KB |
Output is correct |
12 |
Correct |
2721 ms |
319088 KB |
Output is correct |
13 |
Correct |
2220 ms |
308248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
57208 KB |
Output is correct |
2 |
Correct |
38 ms |
57080 KB |
Output is correct |
3 |
Correct |
39 ms |
56960 KB |
Output is correct |
4 |
Correct |
35 ms |
56704 KB |
Output is correct |
5 |
Correct |
2607 ms |
309344 KB |
Output is correct |
6 |
Correct |
1925 ms |
231836 KB |
Output is correct |
7 |
Correct |
1340 ms |
158968 KB |
Output is correct |
8 |
Correct |
613 ms |
72908 KB |
Output is correct |
9 |
Correct |
785 ms |
121316 KB |
Output is correct |
10 |
Correct |
367 ms |
64996 KB |
Output is correct |
11 |
Correct |
781 ms |
121504 KB |
Output is correct |
12 |
Correct |
374 ms |
65120 KB |
Output is correct |
13 |
Correct |
787 ms |
121312 KB |
Output is correct |
14 |
Correct |
365 ms |
64996 KB |
Output is correct |
15 |
Correct |
2670 ms |
318696 KB |
Output is correct |
16 |
Correct |
2224 ms |
308192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
56704 KB |
Output is correct |
2 |
Correct |
37 ms |
56704 KB |
Output is correct |
3 |
Correct |
35 ms |
56696 KB |
Output is correct |
4 |
Correct |
35 ms |
56696 KB |
Output is correct |
5 |
Correct |
36 ms |
56696 KB |
Output is correct |
6 |
Correct |
36 ms |
56828 KB |
Output is correct |
7 |
Correct |
43 ms |
56696 KB |
Output is correct |
8 |
Correct |
257 ms |
63324 KB |
Output is correct |
9 |
Correct |
308 ms |
66772 KB |
Output is correct |
10 |
Correct |
498 ms |
68568 KB |
Output is correct |
11 |
Correct |
1484 ms |
158204 KB |
Output is correct |
12 |
Correct |
1575 ms |
174080 KB |
Output is correct |
13 |
Correct |
1254 ms |
144120 KB |
Output is correct |
14 |
Correct |
2132 ms |
225508 KB |
Output is correct |
15 |
Correct |
1705 ms |
213736 KB |
Output is correct |
16 |
Correct |
36 ms |
56832 KB |
Output is correct |
17 |
Correct |
38 ms |
56696 KB |
Output is correct |
18 |
Correct |
38 ms |
57080 KB |
Output is correct |
19 |
Correct |
37 ms |
57216 KB |
Output is correct |
20 |
Correct |
680 ms |
79608 KB |
Output is correct |
21 |
Correct |
1266 ms |
139880 KB |
Output is correct |
22 |
Correct |
1780 ms |
207572 KB |
Output is correct |
23 |
Correct |
2231 ms |
308104 KB |
Output is correct |
24 |
Correct |
275 ms |
67160 KB |
Output is correct |
25 |
Correct |
308 ms |
67264 KB |
Output is correct |
26 |
Correct |
334 ms |
70344 KB |
Output is correct |
27 |
Correct |
2721 ms |
319088 KB |
Output is correct |
28 |
Correct |
2220 ms |
308248 KB |
Output is correct |
29 |
Correct |
37 ms |
57208 KB |
Output is correct |
30 |
Correct |
38 ms |
57080 KB |
Output is correct |
31 |
Correct |
39 ms |
56960 KB |
Output is correct |
32 |
Correct |
35 ms |
56704 KB |
Output is correct |
33 |
Correct |
2607 ms |
309344 KB |
Output is correct |
34 |
Correct |
1925 ms |
231836 KB |
Output is correct |
35 |
Correct |
1340 ms |
158968 KB |
Output is correct |
36 |
Correct |
613 ms |
72908 KB |
Output is correct |
37 |
Correct |
785 ms |
121316 KB |
Output is correct |
38 |
Correct |
367 ms |
64996 KB |
Output is correct |
39 |
Correct |
781 ms |
121504 KB |
Output is correct |
40 |
Correct |
374 ms |
65120 KB |
Output is correct |
41 |
Correct |
787 ms |
121312 KB |
Output is correct |
42 |
Correct |
365 ms |
64996 KB |
Output is correct |
43 |
Correct |
2670 ms |
318696 KB |
Output is correct |
44 |
Correct |
2224 ms |
308192 KB |
Output is correct |
45 |
Correct |
149 ms |
62032 KB |
Output is correct |
46 |
Correct |
313 ms |
64520 KB |
Output is correct |
47 |
Correct |
961 ms |
136792 KB |
Output is correct |
48 |
Correct |
1635 ms |
186104 KB |
Output is correct |
49 |
Correct |
329 ms |
68424 KB |
Output is correct |
50 |
Correct |
317 ms |
67788 KB |
Output is correct |
51 |
Correct |
372 ms |
70864 KB |
Output is correct |
52 |
Correct |
705 ms |
155980 KB |
Output is correct |
53 |
Correct |
714 ms |
155980 KB |
Output is correct |
54 |
Correct |
712 ms |
155980 KB |
Output is correct |