Submission #997947

#	Time	Username	Problem	Language	Result	Execution time	Memory
997947		pcc	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	2098 ms	65688 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 3e5+10;

int N;
int q;
vector<pair<int,pii>> req;
int ans[mxn];
string state;

struct Q{
	int tp,s,e,val;
	Q(int tt,int ss,int ee,int vv):tp(tt),s(ss),e(ee),val(vv){}
	bool operator<(Q &b)const{
		return s==b.s?tp<b.tp:s<b.s;
	}
};

struct BIT{
	BIT(){}
	int bit[mxn];
	void modify(int p,int v){
		for(;p<mxn;p+=p&-p)bit[p] += v;
		return;
	}
	int getval(int s,int e){
		if(e == -1)swap(s,e);
		int re = 0;
		for(;e>0;e-= e&-e)re += bit[e];
		s--;
		for(;s>0;s-= s&-s)re -= bit[s];
		return re;
	}	
};


vector<Q> v;

namespace INIT{
	set<int> st;
	void GO(){
		st.insert(0);
		st.insert(N+1);
		for(int i = 1;i<=N;i++){
			if(state[i] == '0'){
				st.insert(i);
			}
		}
		for(auto it = next(st.begin());it != st.end();it++){
			int pre = *prev(it)+1;
			int now = *it;
			v.push_back(Q(-1,pre,now,1));
		}
		for(int i = 0;i<q;i++){
			int t = req[i].fs;
			if(t == 0){
				int id = req[i].sc.fs;
				if(st.find(id) == st.end()){
					auto rp = *st.upper_bound(id);
					auto lp = *(--st.upper_bound(id))+1;
					v.push_back(Q(-1,lp,rp,i));
					v.push_back(Q(-1,lp,id,-i));
					v.push_back(Q(-1,id+1,rp,-i));
					st.insert(id);
				}
				else{
					st.erase(id);
					auto rp = *st.upper_bound(id);
					auto lp = *(--st.upper_bound(id))+1;
					v.push_back(Q(-1,lp,id,i));
					v.push_back(Q(-1,id+1,rp,i));
					v.push_back(Q(-1,lp,rp,-i));
				}
			}
			else{
				auto [s,e] = req[i].sc;
				int sh = 0;
				if(*st.lower_bound(s)>=e)sh += i;
				v.push_back(Q(i,s,e,sh));
				ans[i] += sh;
			}
		}
		return;
	}
	void DEBUG(){
		for(auto &i:v){
			cout<<i.tp<<','<<i.s<<' '<<i.e<<' '<<i.val<<endl;
		}
		return;
	}
}

namespace CDQ{
	BIT bit;
	void dc(int l,int r){
		if(l == r)return;
		int mid = (l+r)>>1;
		dc(l,mid);dc(mid+1,r);
		vector<Q> tv;
		vector<int> used = {1};
		for(int i = l;i<=mid;i++){
			if(v[i].tp == -1)tv.push_back(v[i]);
		}
		for(int i = mid+1;i<=r;i++){
			if(v[i].tp != -1)tv.push_back(v[i]);
		}
		sort(tv.begin(),tv.end());
		for(auto &i:tv){
			if(i.tp == -1){
				bit.modify(1,i.val);
				bit.modify(i.e+1,-i.val);
				used.push_back(i.e+1);
			}
			else{
				ans[i.tp] += bit.getval(0,i.e);
			}
		}
		for(auto &i:used)bit.modify(i,-bit.getval(i,i));
		return;
	}

	void GO(){
		dc(0,v.size()-1);
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>q;
	cin>>state;
	state = "#"+state;
	for(int i = 0;i<q;i++){
		string s;
		cin>>s;
		if(s[0] == 't'){
			int id;
			cin>>id;
			req.push_back(make_pair(0,pii(id,id)));
		}
		else{
			int s,e;
			cin>>s>>e;
			req.push_back(make_pair(1,pii(s,e)));
		}
	}
	INIT::GO();
	CDQ::GO();
	for(int i = 0;i<q;i++){
		if(req[i].fs)cout<<ans[i]<<'\n';
	}
	return 0;
}

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