#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int, int>
#define f first
#define s second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<" "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x ){ cerr<<x<<endl; }
template<typename T, typename ...S> void _do(T && x , S&&...y){ cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT
const int maxn = 3e5+5;
//vector<pii> g[maxn];
int n,q;
bool hi[maxn];
int ps[maxn];
int ans[maxn], lt[maxn];
struct con{
// connected group of 1s
int l,r,t; // l, r, time when it was created
bool operator < (const con &oth) const{
return l!=oth.l?l<oth.l:(tie(r,t) < tie(oth.r, oth.t));
}
};
struct BIT{
int mxn = 0;
vector<int> s;
ll QU(int e) {
ll re = 0; for (++e; e>0; e-=e&-e) re += s[e]; return re;
}
void MO(int e, ll v) {
for (++e; e<mxn; e+=e&-e) s[e] += v;
}
BIT(int xx) {
mxn = xx+1; s.resize(mxn+1);
}
BIT(){
}
};
vector<int> hvq[maxn];
BIT bb[maxn];
ll QU(int e, int y){
ll re = 0;
for (++e; e>0; e-=e&-e) {
int xx = upper_bound(ALL(hvq[e]),y) - hvq[e].begin() -1;
re += bb[e].QU(xx);
}
return re;
}
void MO(int e, int y, ll v) {
for (++e; e<maxn; e+=e&-e) {
int xx = upper_bound(ALL(hvq[e]),y)-hvq[e].begin()-1;
bb[e].MO(xx,v);
}
}
int NOWI = 0;
vector<array<int, 3> > mos[maxn];
void PMO(int e, int y, ll v) {
mos[NOWI].pb({{e,y,v}});
for (++e; e<maxn; e+=e&-e) {
hvq[e].pb(y);
}
}
set<con> st;
void dump(){
#ifdef BALBIT
for (auto & c : st) {
cout<<"("<<c.l<<","<<c.r<<")- "<<c.t<<endl;
}
#endif
}
signed main(){
IOS();
cin>>n>>q;
int tmpl = 0;
for (int i = 0; i<=n; ++i) {
char c='0'; if (i!=n)cin>>c;
hi[i] = c=='1';
if (!hi[i]) {
if(tmpl <= i-1) {
st.insert({tmpl, i-1, -1});
}
tmpl = i+1;
}
}
dump();
// done building segments
vector<pii> ques; // if a is -1, b is x
for (int i = 0; i<q; ++i) {
NOWI = i;
string tp; cin>>tp;
if (tp[0] == 'q') {
int a,b; cin>>a>>b; --a; --b; --b;
ques.pb({a,b});
auto it = st.upper_bound({a,100000000,-1});
if (it != st.begin()) {
--it;
bug("HI?");
if (it->r >= b) {
bug(i,"OIJEWFOIWJE");
ans[i] += i - it->t;
}
}
}else{
int x; cin>>x; --x;
ques.pb({-1,x});
if (hi[x]) {
// turn off (break segment)
bug("Hiii");
auto it = (st.upper_bound({x,100000000,-1}));
// if (it == st.begin()) while (1);
--it;
con tmp = *it;
// use it to update
PMO((it->l), n - it->r, i - it->t);
if (tmp. l <= x-1) st.insert({tmp.l, x-1, i});
if (x+1 <= tmp.r) st.insert({x+1, tmp.r, i});
st.erase(tmp);
}else{
// merge??????????????
con ns = {x,x,i};
auto it = (st.upper_bound({x,-1,-1}));
if (it != st.begin()) {
--it;
if (it -> r == x-1) {
PMO((it->l), n - it->r, i - it->t);
// merge!
ns.l = it->l;
st.erase(it);
}
}
it = (st.upper_bound({x,-1,-1}));
if (it != st.end()) {
if (it->l == x+1) {
PMO((it->l), n- it->r, i - it->t);
ns.r = it->r;
st.erase(it);
}
}
st.insert(ns);
}
hi[x] ^= 1;
}
dump();
}
for (int i =0 ; i<maxn; ++i) {
bb[i] = BIT(SZ(hvq[i]));
sort(ALL(hvq[i]));
}
for (int i = 0; i<q; ++i) {
if (ques[i].f == -1) {
// is a toggle
int x=ques[i].s;
for (auto a : mos[i]) {
MO(a[0], a[1], a[2]);
bug(a[0], a[1], a[2]);
}
}else{
int l = ques[i].f, r = ques[i].s;
ll lol = QU(l, n - r);
bug(ans[i], lol);
cout<<ans[i]+lol<<endl;
}
}
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:180:17: warning: unused variable 'x' [-Wunused-variable]
int x=ques[i].s;
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
33272 KB |
Output is correct |
2 |
Correct |
35 ms |
33272 KB |
Output is correct |
3 |
Correct |
33 ms |
33272 KB |
Output is correct |
4 |
Correct |
34 ms |
33272 KB |
Output is correct |
5 |
Correct |
34 ms |
33280 KB |
Output is correct |
6 |
Correct |
31 ms |
33272 KB |
Output is correct |
7 |
Correct |
31 ms |
33280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
850 ms |
88676 KB |
Output is correct |
2 |
Correct |
924 ms |
88912 KB |
Output is correct |
3 |
Correct |
1031 ms |
83280 KB |
Output is correct |
4 |
Correct |
1167 ms |
82220 KB |
Output is correct |
5 |
Correct |
1340 ms |
87672 KB |
Output is correct |
6 |
Correct |
1253 ms |
88380 KB |
Output is correct |
7 |
Correct |
172 ms |
42072 KB |
Output is correct |
8 |
Correct |
179 ms |
45780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
33528 KB |
Output is correct |
2 |
Correct |
36 ms |
33536 KB |
Output is correct |
3 |
Correct |
35 ms |
33536 KB |
Output is correct |
4 |
Correct |
33 ms |
33280 KB |
Output is correct |
5 |
Correct |
1581 ms |
102480 KB |
Output is correct |
6 |
Correct |
1492 ms |
95196 KB |
Output is correct |
7 |
Correct |
1124 ms |
82064 KB |
Output is correct |
8 |
Correct |
175 ms |
46164 KB |
Output is correct |
9 |
Correct |
113 ms |
42600 KB |
Output is correct |
10 |
Correct |
129 ms |
43476 KB |
Output is correct |
11 |
Correct |
130 ms |
43604 KB |
Output is correct |
12 |
Correct |
172 ms |
42452 KB |
Output is correct |
13 |
Correct |
196 ms |
46164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
33268 KB |
Output is correct |
2 |
Correct |
30 ms |
33408 KB |
Output is correct |
3 |
Correct |
34 ms |
33536 KB |
Output is correct |
4 |
Correct |
33 ms |
33536 KB |
Output is correct |
5 |
Correct |
356 ms |
45116 KB |
Output is correct |
6 |
Correct |
887 ms |
64992 KB |
Output is correct |
7 |
Correct |
1462 ms |
84176 KB |
Output is correct |
8 |
Correct |
1902 ms |
109120 KB |
Output is correct |
9 |
Correct |
1401 ms |
104800 KB |
Output is correct |
10 |
Correct |
1532 ms |
133916 KB |
Output is correct |
11 |
Correct |
1280 ms |
104976 KB |
Output is correct |
12 |
Correct |
1501 ms |
132560 KB |
Output is correct |
13 |
Correct |
1345 ms |
104912 KB |
Output is correct |
14 |
Correct |
1544 ms |
132020 KB |
Output is correct |
15 |
Correct |
187 ms |
43476 KB |
Output is correct |
16 |
Correct |
205 ms |
47192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
33272 KB |
Output is correct |
2 |
Correct |
35 ms |
33272 KB |
Output is correct |
3 |
Correct |
33 ms |
33272 KB |
Output is correct |
4 |
Correct |
34 ms |
33272 KB |
Output is correct |
5 |
Correct |
34 ms |
33280 KB |
Output is correct |
6 |
Correct |
31 ms |
33272 KB |
Output is correct |
7 |
Correct |
31 ms |
33280 KB |
Output is correct |
8 |
Correct |
850 ms |
88676 KB |
Output is correct |
9 |
Correct |
924 ms |
88912 KB |
Output is correct |
10 |
Correct |
1031 ms |
83280 KB |
Output is correct |
11 |
Correct |
1167 ms |
82220 KB |
Output is correct |
12 |
Correct |
1340 ms |
87672 KB |
Output is correct |
13 |
Correct |
1253 ms |
88380 KB |
Output is correct |
14 |
Correct |
172 ms |
42072 KB |
Output is correct |
15 |
Correct |
179 ms |
45780 KB |
Output is correct |
16 |
Correct |
32 ms |
33528 KB |
Output is correct |
17 |
Correct |
36 ms |
33536 KB |
Output is correct |
18 |
Correct |
35 ms |
33536 KB |
Output is correct |
19 |
Correct |
33 ms |
33280 KB |
Output is correct |
20 |
Correct |
1581 ms |
102480 KB |
Output is correct |
21 |
Correct |
1492 ms |
95196 KB |
Output is correct |
22 |
Correct |
1124 ms |
82064 KB |
Output is correct |
23 |
Correct |
175 ms |
46164 KB |
Output is correct |
24 |
Correct |
113 ms |
42600 KB |
Output is correct |
25 |
Correct |
129 ms |
43476 KB |
Output is correct |
26 |
Correct |
130 ms |
43604 KB |
Output is correct |
27 |
Correct |
172 ms |
42452 KB |
Output is correct |
28 |
Correct |
196 ms |
46164 KB |
Output is correct |
29 |
Correct |
38 ms |
33268 KB |
Output is correct |
30 |
Correct |
30 ms |
33408 KB |
Output is correct |
31 |
Correct |
34 ms |
33536 KB |
Output is correct |
32 |
Correct |
33 ms |
33536 KB |
Output is correct |
33 |
Correct |
356 ms |
45116 KB |
Output is correct |
34 |
Correct |
887 ms |
64992 KB |
Output is correct |
35 |
Correct |
1462 ms |
84176 KB |
Output is correct |
36 |
Correct |
1902 ms |
109120 KB |
Output is correct |
37 |
Correct |
1401 ms |
104800 KB |
Output is correct |
38 |
Correct |
1532 ms |
133916 KB |
Output is correct |
39 |
Correct |
1280 ms |
104976 KB |
Output is correct |
40 |
Correct |
1501 ms |
132560 KB |
Output is correct |
41 |
Correct |
1345 ms |
104912 KB |
Output is correct |
42 |
Correct |
1544 ms |
132020 KB |
Output is correct |
43 |
Correct |
187 ms |
43476 KB |
Output is correct |
44 |
Correct |
205 ms |
47192 KB |
Output is correct |
45 |
Correct |
340 ms |
71800 KB |
Output is correct |
46 |
Correct |
483 ms |
69884 KB |
Output is correct |
47 |
Correct |
778 ms |
64352 KB |
Output is correct |
48 |
Correct |
1135 ms |
81368 KB |
Output is correct |
49 |
Correct |
130 ms |
44376 KB |
Output is correct |
50 |
Correct |
124 ms |
44116 KB |
Output is correct |
51 |
Correct |
129 ms |
44632 KB |
Output is correct |
52 |
Correct |
138 ms |
44184 KB |
Output is correct |
53 |
Correct |
143 ms |
43604 KB |
Output is correct |
54 |
Correct |
130 ms |
44520 KB |
Output is correct |