#include<bits/stdc++.h>
using namespace std;
struct Fenwick
{
vector<int> s;
Fenwick(int n) : s(n+1){}
int qry(int poz)
{
int aux=0;
for(int i=poz;i<s.size();i+=(i&(-i)))
aux += s[i];
return aux;
}
void upd(int poz, int newv)
{
for(int i=poz;i>0;i-=(i&(-i)))
s[i] += newv;
}
};
struct FT2
{
vector<pair<pair<int,int>,int>> upds;
vector<vector<int>> ys;
vector<Fenwick> ft;
FT2(int limx) : ys(limx+1){}
void fake_upd(int pozx, int pozy)
{
return;///-------------------------------------------------------------------------------------------------------------------------------
for(int i=pozx;i<ys.size();i+=(i&(-i)))
ys[i].push_back(pozy);
}
void init()
{
for(auto v:ys)
{
sort(v.begin(),v.end());
ft.push_back(v.size());
}
}
int ind(int x, int y)
{
return (int)(lower_bound(ys[x].begin(),ys[x].end(),y) - ys[x].begin() + 1);
}
int qry(int pozx, int pozy)
{
int aux=0;
for(auto u:upds)
if(u.first.first <= pozx && u.first.second >= pozy)
aux += u.second;
return aux;
for(int i=pozx;i>0;i-=(i&(-i)))
aux += ft[i].qry(ind(i,pozy));
return aux;
}
void upd(int pozx, int pozy, int newv)
{
upds.push_back({{pozx,pozy},newv});
return;
for(int i=pozx;i<ys.size();i+=(i&(-i)))
ft[i].upd(ind(i,pozy),newv);
}
};
set<pair<pair<int,int>,int>> s;
bool tip[300005];
int cit[300005][2];
signed main()
{
int n,q;
cin>>n>>q;
FT2 old(n),active_sum(n),active_cnt(n);
vector<bool> init(n+2,0);
char ch;
for(int i=1;i<=n;i++)
{
cin>>ch;
if(ch=='1') init[i]=1;
else init[i]=0;
}
vector<bool> stare=init;
int inc=-1;
for(int i=1;i<=n;i++)
{
if(stare[i]==1)
{
if(inc==-1) inc=i;
if(i==n || stare[i+1]==0)
{
s.insert({{inc,i},0});
active_cnt.fake_upd(inc,i);
active_sum.fake_upd(inc,i);
//cout<<inc<<" "<<i<<" in set\n";
inc=-1;
}
}
}
string str;
int a,b;
for(int i=1;i<=q;i++)
{
cin>>str;
if(str=="toggle")
tip[i]=0;
else
tip[i]=1;
if(tip[i]==0)
{
cin>>cit[i][0];
a=cit[i][0];
if(stare[a]==0)
{
int le=a,ri=a;
if(stare[a-1]==1)
{
auto it = prev(s.lower_bound({{a,-1},-1}));
le = (*it).first.first;
s.erase(it);
}
if(stare[a+1]==1)
{
auto it = s.lower_bound({{a,-1},-1});
ri = (*it).first.second;
s.erase(it);
}
s.insert({{le,ri},i});
active_cnt.fake_upd(le,ri);
active_sum.fake_upd(le,ri);
}
else
{
auto it = prev(s.lower_bound({{a,n+1},n+1}));
int le = (*it).first.first, ri = (*it).first.second;
s.erase(it);
if(stare[a-1]==1)
{
s.insert({{le,a-1},i});
old.fake_upd(le,a-1);
active_cnt.fake_upd(le,a-1);
active_sum.fake_upd(le,a-1);
}
if(stare[a+1]==1)
{
s.insert({{a+1,ri},i});
old.fake_upd(a+1,ri);
active_cnt.fake_upd(a+1,ri);
active_sum.fake_upd(a+1,ri);
}
}
stare[a] = 1-stare[a];
}
else
cin>>cit[i][0]>>cit[i][1];
}
stare=init;
s.clear();
old.init();
active_cnt.init();
active_sum.init();
inc=-1;
for(int i=1;i<=n;i++)
{
if(stare[i]==1)
{
if(inc==-1) inc=i;
if(i==n || stare[i+1]==0)
{
s.insert({{inc,i},0});
active_cnt.upd(inc,i,+1);
active_sum.upd(inc,i,0);
inc=-1;
}
}
}
for(int i=1;i<=q;i++)
{
if(tip[i]==0)
{
a=cit[i][0];
if(stare[a]==0)
{
int le=a,ri=a;
if(stare[a-1]==1)
{
auto it = prev(s.lower_bound({{a,-1},-1}));
le = (*it).first.first;
old.upd((*it).first.first,(*it).first.second,i-(*it).second);
active_cnt.upd((*it).first.first,(*it).first.second,-1);
active_sum.upd((*it).first.first,(*it).first.second,-(*it).second);
s.erase(it);
}
if(stare[a+1]==1)
{
auto it = s.lower_bound({{a,-1},-1});
ri = (*it).first.second;
old.upd((*it).first.first,(*it).first.second,i-(*it).second);
active_cnt.upd((*it).first.first,(*it).first.second,-1);
active_sum.upd((*it).first.first,(*it).first.second,-(*it).second);
s.erase(it);
}
s.insert({{le,ri},i});
active_cnt.upd(le,ri,+1);
active_sum.upd(le,ri,i);
}
else
{
auto it = prev(s.lower_bound({{a,n+1},n+1}));
int le = (*it).first.first, ri = (*it).first.second;
old.upd(le,ri,i-(*it).second);
active_cnt.upd(le,ri,-1);
active_sum.upd(le,ri,-(*it).second);
s.erase(it);
if(stare[a-1]==1)
{
s.insert({{le,a-1},i});
active_cnt.upd(le,a-1,+1);
active_sum.upd(le,a-1,i);
}
if(stare[a+1]==1)
{
s.insert({{a+1,ri},i});
active_cnt.upd(a+1,ri,+1);
active_sum.upd(a+1,ri,i);
}
}
stare[a] = 1-stare[a];
}
else
{
a=cit[i][0];
b=cit[i][1];
b--;
int rez=0;
rez += old.qry(a,b);
rez += active_cnt.qry(a,b)*i - active_sum.qry(a,b);
cout<<rez<<"\n";
}
}
return 0;
}
Compilation message
street_lamps.cpp: In member function 'int Fenwick::qry(int)':
street_lamps.cpp:10:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
10 | for(int i=poz;i<s.size();i+=(i&(-i)))
| ~^~~~~~~~~
street_lamps.cpp: In member function 'void FT2::fake_upd(int, int)':
street_lamps.cpp:29:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(int i=pozx;i<ys.size();i+=(i&(-i)))
| ~^~~~~~~~~~
street_lamps.cpp: In member function 'void FT2::upd(int, int, int)':
street_lamps.cpp:61:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i=pozx;i<ys.size();i+=(i&(-i)))
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
444 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5074 ms |
5316 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
2 ms |
604 KB |
Output is correct |
| 3 |
Correct |
3 ms |
600 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
4245 ms |
116772 KB |
Output is correct |
| 6 |
Execution timed out |
5041 ms |
87064 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
600 KB |
Output is correct |
| 2 |
Correct |
2 ms |
604 KB |
Output is correct |
| 3 |
Correct |
3 ms |
812 KB |
Output is correct |
| 4 |
Correct |
2 ms |
860 KB |
Output is correct |
| 5 |
Execution timed out |
5094 ms |
90684 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
444 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Execution timed out |
5074 ms |
5316 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
