Submission #197912

#	Time	Username	Problem	Language	Result	Execution time	Memory
197912		TAISA_	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2948 ms	269288 KiB

street_lamps

#include <bits/stdc++.h>
#define mp make_pair
#define all(v) v.begin(),v.end()
using namespace std;
using ll=long long;
using vi=vector<ll>;
using P=pair<int,int>;
struct BIT{
	vector<int> dat;
	void build(int n){
		dat.resize(n+1,0);
	}
	void add(int k,int x){
		for(++k;k<dat.size();k+=k&-k){
			dat[k]+=x;
		}
	}
	int get(int k){
		int res=0;
		for(++k;k>0;k-=k&-k){
			res+=dat[k];
		}
		return res;
	}
};
struct Segtree{
	int n;
	vector<BIT> dat;
	vector<vector<int>> ds,ls,rs;
	Segtree(int n_){
		n=1;
		while(n<n_)n<<=1;
		ds.resize(2*n);
		ls.resize(2*n);
		rs.resize(2*n);
		dat.resize(2*n);
	}
	void preupd(int x,int y){
		ds[x+n].push_back(y);
	}
	void build(){
		for(int k=2*n-1;k>=n;k--){
			sort(all(ds[k]));
			ds[k].erase(unique(all(ds[k])),ds[k].end());
		}
		for(int k=n-1;k>0;k--){
			ds[k].resize(ds[k<<1].size()+ds[k<<1|1].size());
			merge(all(ds[k<<1]),all(ds[k<<1|1]),ds[k].begin());
			ds[k].erase(unique(all(ds[k])),ds[k].end());
			ls[k].resize(ds[k].size()+1);
			rs[k].resize(ds[k].size()+1);
			int t1=0,t2=0;
			for(int i=0;i<ds[k].size();i++){
				while(t1<ds[k<<1].size()&&ds[k<<1][t1]<ds[k][i])++t1;
				while(t2<ds[k<<1|1].size()&&ds[k<<1|1][t2]<ds[k][i])++t2;
				ls[k][i]=t1;
				rs[k][i]=t2;
			}
			ls[k][ds[k].size()]=ds[k<<1].size();
			rs[k][ds[k].size()]=ds[k<<1|1].size();
		}
		for(int k=0;k<2*n-1;k++){
			dat[k].build(ds[k].size());
		}
	}
	void upd(int x,int y,int z){
		int k=x+n;
		int yy=lower_bound(all(ds[k]),y)-ds[k].begin();
		dat[k].add(yy,z);
		k>>=1;
		while(k>0){
			yy=lower_bound(all(ds[k]),y)-ds[k].begin();
			dat[k].add(yy,z);
			k>>=1;
		}
	}
	int get(int a,int b,int x,int y,int k,int l,int r){
		if(b<=l||r<=a){
			return 0;
		}
		if(a<=l&&r<=b){
			return dat[k].get(y-1)-dat[k].get(x-1);
		}
		return get(a,b,ls[k][x],ls[k][y],k<<1,l,(l+r)>>1)+
				get(a,b,rs[k][x],rs[k][y],k<<1|1,(l+r)>>1,r);
	}
	inline int get(int a,int b,int x,int y){
		x=lower_bound(all(ds[1]),x)-ds[1].begin();
		y=lower_bound(all(ds[1]),y)-ds[1].begin();
		return get(a,b,x,y,1,0,n);
	}
};
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,q;cin>>n>>q;
	string str;cin>>str;
	int b=-1;
	Segtree seg(n+10);
	set<pair<P,int>> st;
	vector<P> vi;
	for(int i=0;i<n;i++){
		if(str[i]=='1'){
			if(b==-1){
				b=i;
			}
		}else{
			if(b!=-1){
				st.insert(mp(P(b,i-1),-1));
				seg.preupd(b,i-1);
				b=-1;
			}
		}
	}
	if(b!=-1){
		st.insert(mp(P(b,n-1),-1));
		seg.preupd(b,n-1);
	}
	vector<vector<pair<P,int>>> vs(q);
	vector<int> res(q),aa(q,-1),bb(q);
	for(int i=0;i<q;i++){
		string t;cin>>t;
		if(t=="toggle"){
			int a;cin>>a;--a;
			auto add=[&](pair<P,int> p){
				st.erase(p);
				seg.preupd(p.first.first,p.first.second);
				vs[i].emplace_back(p.first,p.second);
			};
			auto ins=[&](pair<P,int> p){
				if(p.first.first<=p.first.second){
					st.insert(p);
				}
			};
			if(str[a]=='0'){
				str[a]='1';
				pair<P,int> to=mp(P(a,a),i);
				if(st.empty()){
					ins(to);
					continue;
				}
				auto ir=st.lower_bound(to);
				if(ir!=st.end()&&(*ir).first.first==a+1){
					to.first.second=(*ir).first.second;
					add(*ir);
				}
				auto il=st.lower_bound(to);
				if(il!=st.begin()){
					--il;
					if((*il).first.second==a-1){
						to.first.first=(*il).first.first;
						add(*il);
					}
				}
				ins(to);
			}else{
				str[a]='0';
				auto it=prev(st.lower_bound(mp(P(a+1,-1),-1)));
				pair<P,int> p=(*it);
				add(*it);
				ins(mp(P(p.first.first,a-1),i));
				ins(mp(P(a+1,p.first.second),i));
			}
		}else{
			int a;cin>>a>>b;--a;--b;--b;
			aa[i]=a,bb[i]=b;
			seg.preupd(0,a+1);
			seg.preupd(b,n);
			auto it=st.lower_bound(mp(P(a+1,-1),-1));
			if(!st.empty()&&it!=st.begin()){
				--it;
				if((*it).first.first<=a&&b<=(*it).first.second){
					res[i]+=i-(*it).second;
				}
			}
		}	
	}
	seg.build();
	for(int i=0;i<q;i++){
		if(aa[i]==-1){
			for(auto &e:vs[i]){
		//		cout<<e.first.first<<" "<<e.first.second<<" "<<i-e.second<<endl;
				seg.upd(e.first.first,e.first.second,i-e.second);
			}
		}else{
			res[i]+=seg.get(0,aa[i]+1,bb[i],n);
			//cout<<0<<" "<<aa[i]<<" "<<bb[i]<<" "<<n-1<<" "<<seg.get(0,aa[i]+1,bb[i],n)<<endl;
			cout<<res[i]<<'\n';
		}
	}	
}

Compilation message (stderr)

street_lamps.cpp: In member function 'void BIT::add(int, int)':
street_lamps.cpp:14:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(++k;k<dat.size();k+=k&-k){
           ~^~~~~~~~~~~
street_lamps.cpp: In member function 'void Segtree::build()':
street_lamps.cpp:53:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<ds[k].size();i++){
                ~^~~~~~~~~~~~~
street_lamps.cpp:54:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(t1<ds[k<<1].size()&&ds[k<<1][t1]<ds[k][i])++t1;
           ~~^~~~~~~~~~~~~~~~
street_lamps.cpp:55:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(t2<ds[k<<1|1].size()&&ds[k<<1|1][t2]<ds[k][i])++t2;
           ~~^~~~~~~~~~~~~~~~~~

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