#include <bits/stdc++.h>
using namespace std;
const int nmax = 3e5;
const int oo = INT_MAX;
int n,q;
int v[nmax + 5];
int t[nmax + 5];
pair<int,int> qry[nmax + 5];
int rez[nmax + 5];
set<pair<pair<int,int>,int>> s_st;
set<pair<pair<int,int>,int>, greater<pair<pair<int,int>,int>>> s_dr;
vector<pair<pair<int,int>,int>> upd[nmax + 5];
int ai[4 * nmax + 5];
int lazy[4 * nmax + 5];
void propag(int nod)
{
if(lazy[nod] == 0)
{
return;
}
ai[nod * 2] = ai[nod * 2 + 1] = lazy[nod];
lazy[nod * 2] = lazy[nod * 2 + 1] = lazy[nod];
lazy[nod] = 0;
}
void update(int ua, int ub, int val, int nod, int a, int b)
{
if(ua <= a && ub>=b)
{
ai[nod] = val;
lazy[nod] = val;
return;
}
propag(nod);
int mij = (a + b) >> 1;
if(ua <= mij)
{
update(ua,ub,val,nod*2,a,mij);
}
if(ub > mij)
{
update(ua,ub,val,nod*2+1,mij+1,b);
}
ai[nod] = max(ai[nod * 2], ai[nod * 2 + 1]);
}
int query(int qa, int qb, int nod, int a, int b)
{
if(qa <= a && qb >= b)
{
return ai[nod];
}
propag(nod);
int mij = (a + b) >> 1;
if(qa<=mij && qb>mij)
{
return max(query(qa,qb,nod*2,a,mij), query(qa,qb,nod*2+1,mij+1,b));
}
if(qa<=mij)
{
return query(qa,qb,nod*2,a,mij);
}
return query(qa,qb,nod*2+1,mij+1,b);
}
vector<int> aib[nmax + 5], aib_lst[nmax + 5];
int ub(int x)
{
return (x & (-x));
}
void simulate_update(int poz_st, int poz_dr)
{
for(int i=poz_st;i<=n;i+=ub(i))
{
aib_lst[i].push_back(poz_dr);
}
}
void update_aib(int poz_st, int poz_dr, int val)
{
for(int i=poz_st; i<=n; i+=ub(i))
{
int st = 1;
int dr = aib_lst[i].size() - 1;
int poz = 0;
while(st<=dr)
{
int mij = (st + dr) >> 1;
if(aib_lst[i][mij] <= poz_dr)
{
poz = mij;
st = mij + 1;
}
else
{
dr = mij - 1;
}
}
for(int j=poz; j<=aib_lst[i].size()-1; j+=ub(j))
{
aib[i][j] += val;
}
}
}
int query_aib(int poz_st, int poz_dr)
{
int rez = 0;
for(int i=poz_st;i>=1;i-=ub(i))
{
int st = 1;
int dr = aib_lst[i].size() - 1;
int poz = 0;
while(st<=dr)
{
int mij = (st + dr) >> 1;
if(aib_lst[i][mij] < poz_dr)
{
poz = mij;
st = mij + 1;
}
else
{
dr = mij - 1;
}
}
for(int j=aib_lst[i].size()-1;j>=1;j-=ub(j))
{
rez += aib[i][j];
}
for(int j=poz;j>=1;j-=ub(j))
{
rez -= aib[i][j];
}
}
return rez;
}
void Remove_segment(int st, int dr, int i)
{
auto it_st = s_st.lower_bound({{st,dr}, 0});
auto it_dr = s_dr.lower_bound({{st,dr}, oo});
int nr = it_st -> second;
upd[i].push_back({{st,dr}, i - nr});
s_st.erase(it_st);
s_dr.erase(it_dr);
}
void Add(int poz, int i)
{
update(poz,poz,i,1,1,n);
int st = poz, dr = poz;
auto it_dr = s_dr.lower_bound({{poz, oo}, 0});
if(it_dr != s_dr.end() && it_dr->first.second == poz - 1)
{
st = it_dr->first.first;
update(it_dr->first.first, it_dr->first.second, i, 1,1,n);
Remove_segment(it_dr->first.first, it_dr->first.second, i);
}
auto it_st = s_st.lower_bound({{poz, 0}, 0});
if(it_st != s_st.end() && it_st->first.first == poz + 1)
{
dr = it_st->first.second;
update(it_st->first.first, it_st->first.second, i, 1,1,n);
Remove_segment(it_st->first.first, it_st->first.second, i);
}
s_st.insert({{st,dr},i});
s_dr.insert({{st,dr},i});
}
void Rem(int poz, int i)
{
update(poz,poz,oo,1,1,n);
auto it = s_dr.lower_bound({{poz, oo}, 0});
int st = it->first.first;
int dr = it->first.second;
Remove_segment(st, dr, i);
if(st != poz)
{
s_st.insert({{st, poz - 1}, i});
s_dr.insert({{st, poz - 1}, i});
}
if(dr != poz)
{
s_st.insert({{poz + 1, dr}, i});
s_dr.insert({{poz + 1, dr}, i});
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
#ifdef home
freopen("nr.in","r",stdin);
freopen("nr.out","w",stdout);
#endif // home
cin>>n>>q;
for(int i=1; i<=n; i++)
{
char ch;
cin>>ch;
v[i] = ch - '0';
}
int st = 1, dr = 0;
for(int i=1; i<=n; i++)
{
if(v[i] == 1)
{
dr = i;
}
else
{
if(st <= dr)
{
s_st.insert({{st,dr}, 0});
s_dr.insert({{st,dr}, 0});
}
st = i + 1;
}
}
if(st <= dr)
{
s_st.insert({{st,dr}, 0});
s_dr.insert({{st,dr}, 0});
}
for(int i=1; i<=n; i++)
{
if(v[i] == 1)
{
update(i,i, 0, 1,1,n);
}
else
{
update(i,i, oo, 1,1,n);
}
}
for(int i=1; i<=q; i++)
{
string tip;
cin>>tip;
if(tip == "query")
{
t[i] = 0;
cin>>qry[i].first>>qry[i].second;
--qry[i].second;
int a = qry[i].first, b = qry[i].second;
int last = query(a,b,1,1,n);
if(last != oo)
{
rez[i] += i - last;
}
}
else
{
t[i] = 1;
cin>>qry[i].first;
int poz = qry[i].first;
if(v[poz] == 0)
{
v[poz] = 1;
Add(poz,i);
}
else
{
v[poz] = 0;
Rem(poz,i);
}
}
}
for(int i=1; i<=q; i++)
{
for(auto it : upd[i])
{
int st = it.first.first;
int dr = it.first.second;
int val = it.second;
simulate_update(st,dr);
}
}
for(int i=1; i<=n; i++)
{
aib_lst[i].push_back(0);
aib[i].resize(aib_lst[i].size());
sort(aib_lst[i].begin(),aib_lst[i].end());
}
for(int i=1; i<=q; i++)
{
if(t[i] == 0)
{
int st = qry[i].first, dr = qry[i].second;
rez[i] += query_aib(st, dr);
cout<<rez[i]<<'\n';
}
else
{
for(auto it : upd[i])
{
int st = it.first.first;
int dr = it.first.second;
int val = it.second;
update_aib(st,dr,val);
}
}
}
return 0;
}
Compilation message
street_lamps.cpp: In function 'void update_aib(int, int, int)':
street_lamps.cpp:111:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(int j=poz; j<=aib_lst[i].size()-1; j+=ub(j))
| ~^~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:289:17: warning: unused variable 'val' [-Wunused-variable]
289 | int val = it.second;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
29276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
269 ms |
42536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
29284 KB |
Output is correct |
| 2 |
Correct |
8 ms |
29524 KB |
Output is correct |
| 3 |
Correct |
8 ms |
29280 KB |
Output is correct |
| 4 |
Correct |
7 ms |
29368 KB |
Output is correct |
| 5 |
Correct |
1696 ms |
88620 KB |
Output is correct |
| 6 |
Correct |
1575 ms |
85316 KB |
Output is correct |
| 7 |
Correct |
1253 ms |
79064 KB |
Output is correct |
| 8 |
Correct |
317 ms |
62940 KB |
Output is correct |
| 9 |
Correct |
88 ms |
32920 KB |
Output is correct |
| 10 |
Correct |
90 ms |
33220 KB |
Output is correct |
| 11 |
Correct |
92 ms |
33548 KB |
Output is correct |
| 12 |
Correct |
251 ms |
61408 KB |
Output is correct |
| 13 |
Correct |
269 ms |
62960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
29472 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
29272 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
29276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
