Submission #756112

#	Time	Username	Problem	Language	Result	Execution time	Memory
756112		boyliguanhan	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	303 ms	1364 KiB

street_lamps

#include<bits/stdc++.h>
using namespace std;
#define N 13000100
#define mid ((lb+rb)>>1)
int root[300100], n, q, on[300100], sum[N], ch[N][2], cnt;
void upd1(int &rt,int lb,int rb,int pos,int w){
	if (!rt) rt=++cnt;sum[rt]+=w;
	if (lb==rb) return;
	(mid>=pos?upd1(ch[rt][0],lb,mid,pos,w):upd1(ch[rt][1],mid+1,rb,pos,w));
}
int query1(int rt,int lb,int rb,int l,int r){
	if (!rt||lb>r||rb<l) return 0;
	if (l>=lb&&rb<=r) return sum[rt];
	return query1(ch[rt][0],lb,mid,l,r)+query1(ch[rt][1],mid+1,rb,l,r);
}
inline void upd2(int pos,int r,int w){
	while(pos<=n+1)
        upd1(root[pos],1,n+1,r,w),pos+=pos&-pos;
}
inline int query2(int x,int y){
	int ans=0;
	while(x)
        ans+=query1(root[x],1,n+1,1,y),x-=x&-x;
	return ans;
}
inline void upd3(int x1, int y1, int x2, int y2, int W) {
    upd2(x1, y1, W);
    upd2(x1, y2 + 1, -W);
    upd2(x2 + 1, y1, -W);
    upd2(x2 + 1, y2 + 1, W);
}
struct seg{
    int l, r;
};
inline bool operator < (seg a,seg b){
	return a.r<b.r;
} 
set<seg> st;
int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    n++;
    string str;
    cin >> str;
    for (int i=1;i<=n;i++){
		st.insert((seg){i,i});
	}
	for (int i=1;i<n;i++){
		on[i]=(str[i-1]-48);
		if (on[i]){
            auto it = --st.lower_bound((seg){0,i+1});
			int l = it->l; st.erase(it);
			st.erase((seg){i+1,i+1});
			st.insert((seg){l,i+1});
		}
	}
    for(auto i: st)
        upd3(i.l,i.l,i.r,i.r,q);
    for (int t=1;t<=q;t++){
		cin >> str;
		if (str=="query"){
			int x, y;
            cin >> x >> y;
			int ans=query2(x,y);
			x=(*(st.lower_bound((seg){0,x}))).l;
			y=(*(st.lower_bound((seg){0,y}))).l;
			cout << (ans-(q-t)*(x==y)) << '\n';
		} else {
			int x;
            cin >> x;
			auto it=st.lower_bound((seg){0,x});
			int lb1=it->l,rb1=x;
            if(!on[x]) it++;
			int lb2=x+1,rb2=it->r;
			upd3(lb1,lb2,rb1,rb2,(on[x]?t-q:q-t));
            if(on[x]) {
				st.erase((seg){lb1,rb2});
				st.insert((seg){lb1,rb1});
                st.insert((seg){lb2,rb2}); 
            } else {
				st.erase((seg){lb1,rb1});
                st.erase((seg){lb2,rb2});
				st.insert((seg){lb1,rb2}); 
            }
			on[x]^=1;
		}
	}
}

Compilation message (stderr)

street_lamps.cpp: In function 'void upd1(int&, int, int, int, int)':
street_lamps.cpp:7:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    7 |  if (!rt) rt=++cnt;sum[rt]+=w;
      |  ^~
street_lamps.cpp:7:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
    7 |  if (!rt) rt=++cnt;sum[rt]+=w;
      |                    ^~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20