Submission #756682

#	Time	Username	Problem	Language	Result	Execution time	Memory
756682		boyliguanhan	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	2 ms	340 KiB

street_lamps

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
#define doi(x) cout << #x << " = " << x << '\n'
using namespace std;
#define N 15000100
#define mid ((rl+rr)>>1)
int root[300100], n, q, on[300100], sum[N], ch[N][2], cnt;
void upd1(int &rt,int rl,int rr,int x,int w){
	if (!rt) rt=++cnt;sum[rt]+=w;
	if (rl==rr) return;
	(mid>=x?upd1(ch[rt][0],rl,mid,x,w):upd1(ch[rt][1],mid+1,rr,x,w));
}
int query1(int rt,int rl,int rr,int l,int r){
	if (!rt||rl>r||rr<l) return 0;
	if (rl>=l&&rr<=r) return sum[rt];
	return query1(ch[rt][0],rl,mid,l,r)+query1(ch[rt][1],mid+1,rr,l,r);
}
inline void upd2(int x,int r,int w){
	while(x<=n+1)
        upd1(root[x],1,n+1,r,w),x+=x&-x;
}
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);
    query2(5,6);
    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() {
    freopen("1.in", "r", stdin);
    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)
        if(on[i.l])
            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:9:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    9 |  if (!rt) rt=++cnt;sum[rt]+=w;
      |  ^~
street_lamps.cpp:9:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
    9 |  if (!rt) rt=++cnt;sum[rt]+=w;
      |                    ^~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen("1.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~

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