#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;
}
};
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; 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(){
for (auto & c : st) {
cout<<"("<<c.l<<","<<c.r<<")- "<<c.t<<endl;
}
}
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,-1,-1});
if (it != st.begin()) {
--it;
if (it->r >= b) {
ans[i] += i - it->t;
}
}
}else{
int x; cin>>x; --x;
ques.pb({-1,x});
if (hi[x]) {
// turn off (break segment)
auto it = (st.upper_bound({x,-1,-1}));
if (it == st.begin()) while (1);
--it;
// use it to update
PMO((it->l), n - it->r, i - it->t);
if (it -> l <= x-1) st.insert({it->l, x-1, i});
if (x+1 <= it->r) st.insert({x+1, it->r, i});
st.erase(it);
}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);
}
}
}
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]);
}
}else{
int l = ques[i].f, r = ques[i].s;
ll lol = QU(l, n - r);
cout<<ans[i]+lol<<endl;
}
}
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:171:17: warning: unused variable 'x' [-Wunused-variable]
int x=ques[i].s;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5037 ms |
23800 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5068 ms |
23808 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
33528 KB |
Output is correct |
| 2 |
Incorrect |
47 ms |
33536 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
33280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5037 ms |
23800 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
