제출 #209341

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
209341		Segtree	가로등 (APIO19_street_lamps)	C++14	0 / 100	5072 ms	187896 KiB

street_lamps

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef unordered_set<ll> uset;
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=0;i<=n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define lo(x,y) lower_bound(x.begin(),x.end(),y)-x.begin()
#define all(x) x.begin(),x.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("unroll-loops")
#pragma gcc target("avx2,see4")
#define N (1<<19)
ll q,typ[N],L[N],R[N],S[N],T[N],VAL[N];
typedef struct segtree2D{
	typedef struct segtree{//区間加算、区間和
		ll *dat,*laz,*wid;
		ll n;
		void init(vector<ll> values){//values[i+1]-values[i]の長さのものが|values|-1個並んでる
			n=values.size();//配列外参照を防ぐため+1
			dat=new ll[2*n];
			laz=new ll[2*n];
			wid=new ll[2*n];
			rep(i,2*n)dat[i]=laz[i]=wid[i]=0;
			for(int i=0;i<n-1;i++)wid[i+n]=values[i+1]-values[i];
			for(int i=n-1;i>0;i--)wid[i]=wid[i*2]+wid[i*2+1];
		}
		ll eval(ll k){
			if(k<n){
				laz[k*2]+=laz[k];
				laz[k*2+1]+=laz[k];
			}
			dat[k]+=laz[k]*wid[k],laz[k]=0;
			return dat[k];
		}
		void add(ll l,ll r,ll val){//[l,r),非再起注意
			l+=n,r+=n;
			for(ll a=l,b=r;a<b;a>>=1,b>>=1){
				if(a&1)laz[a++]+=val;
				if(b&1)laz[--b]+=val;
			}
			for(ll a=l,b=r;a+b;a>>=1,b>>=1){
				dat[a/2]=eval(a)+eval(a^1);
				dat[b/2]=eval(b)+eval(b^1);
			}
		}
		ll sum(ll l,ll r){//[l,r),非再起注意
			l+=n,r+=n;
			for(ll d=20;~d;d--){
				eval(l>>d);
				eval(r>>d);
			}
			ll res=0;
			for(ll a=l,b=r;a<b;a>>=1,b>>=1){
				if(a&1)res+=eval(a),a++;
				if(b&1)b--,res+=eval(b);
			}
			return res;
		}
	}segtree;
	segtree seg[2*N];
	vector<ll> values[2*N];
	vector<ll> solve(){
		rep(i,q){
			if(typ[i]==0){//[s,s]*[l,r)にvalを加算
				for(ll x=S[i]+N;x;x>>=1){
					values[x].push_back(L[i]);
					values[x].push_back(R[i]);
				}
			}
			else{//[s,t)*[l,r)の総和を求める
				for(ll a=S[i]+N,b=T[i]+N;a<b;a>>=1,b>>=1){
					if(a&1){
						values[a].push_back(L[i]);
						values[a].push_back(R[i]);
						a++;
					}
					if(b&1){
						b--;
						values[b].push_back(L[i]);
						values[b].push_back(R[i]);
					}
				}
			}
		}
		rep(i,2*N){
			sort(all(values[i]));
			seg[i].init(values[i]);
		}
		vector<ll> fans;
		rep(i,q){
			if(typ[i]==0){//[s,s]*[l,r)にvalを加算
				for(ll x=S[i]+N;x;x>>=1){
					ll LL=lo(values[x],L[i]);
					ll RR=lo(values[x],R[i]);
					seg[x].add(LL,RR,VAL[i]);
				}
			}
			else{//[s,t)*[l,r)の総和を求める
				ll res=0;
				for(ll a=S[i]+N,b=T[i]+N;a<b;a>>=1,b>>=1){
					if(a&1){
						ll LL=lo(values[a],L[i]);
						ll RR=lo(values[a],R[i]);
						res+=seg[a].sum(LL,RR);
						a++;
					}
					if(b&1){
						b--;
						ll LL=lo(values[b],L[i]);
						ll RR=lo(values[b],R[i]);
						res+=seg[b].sum(LL,RR);
					}
				}
				fans.push_back(res);
			}
		}
		return fans;
	}
}segtree2D;
segtree2D seg;

void register_upd(ll t,ll l,ll r,ll val){
	typ[q]=0,L[q]=l,R[q]=r,S[q]=t,T[q]=-1,VAL[q]=val;
	q++;
}
vector<ll> querysid;
void register_sum(ll s,ll t,ll l,ll r,ll id){
	typ[q]=1,L[q]=l,R[q]=r,S[q]=s,T[q]=t;
	querysid.push_back(id);
	q++;
}

typedef struct rng{//[l,r)では[t,t]*[l,r)が1になっている、
	ll l,r,t;
	bool operator<(const rng&key)const{
		return this->l<key.l;
	}
}rng;
set<rng> rngs;//rngの集合、1→nの方向に走査する
void EXAM1(){
	ll res=0;
	for(auto e:rngs)res+=e.r-e.l;
	cerr<<"EXAM:"<<res<<endl;
}
int main(){
	ll n,m;
	string s;
	cin>>n>>m>>s;
	vector<P> zerorng[N];//zerorng[i]:=ランプiが消えている区間[fi,sc)の集合
	vector<P> querys[N];//querys[b]:=右端がbで、a=fiで、id=scのクエリの集合
	{//zerorngとquerysを求める
		ll mas[N];//mas[i]:=ランプiが最後に消されたときの時間、現在光っている時は不要
		for(int i=1;i<=n;i++)if(s[i-1]=='0')mas[i]=0;
		rep(i,m){
			string com;
			cin>>com;
			if(com=="toggle"){
				ll x; cin>>x;
				if(s[x-1]=='0'){
					zerorng[x].push_back(make_pair(mas[x],i+1));
					s[x-1]='1';
				}
				else s[x-1]='0',mas[x]=i;
			}
			if(com=="query"){
				ll a,b; cin>>a>>b;
				querys[b-1].push_back(make_pair(a,i));
			}
		}
		for(int i=1;i<=n;i++){
			if(s[i-1]=='0'){
				zerorng[i].push_back(make_pair(mas[i],m));
			}
		}
	}
	q=0;
	rngs.insert((rng){0,m,0});
	register_upd(0,0,m,+1);
	EXAM1();
	for(int i=1;i<=n;i++){
		for(auto p:zerorng[i]){//ランプが消えている区間のところで、2DSegtreeを更新する。添字がずれている可能性あり
			rng x=(rng){p.first,p.second,i};
			{//元々あったrngを消して、更新クエリを2Dsegtreeに投げる
				auto it=rngs.lower_bound(x);
				while(it!=rngs.end()&&it->l<p.second){
					if(it->r<=p.second){//[p.fi,p.sc)に完全に含まれている
						register_upd(it->t,it->l,it->r,-1);
						it=rngs.erase(it);
					}
					else{//p.fi<=it->l<p.second<it->r
						register_upd(it->t,it->l,p.second,-1);
						rng news=(rng){p.second,it->r,it->t};
						rngs.erase(it);
						rngs.insert(news);
						break;
					}
				}
				it=rngs.lower_bound(x);
				if(it!=rngs.begin()){
					it--;
					if(it->l<=p.first&&p.second<=it->r){//元々あったものの中に、追加するものを完全に含んでいるものがあった
						register_upd(it->t,p.first,p.second,-1);
						rngs.erase(it);
					}
					else{//左側で重なっているもの
						register_upd(it->t,p.first,it->r,-1);
						rng news=(rng){it->l,p.first,it->t};
						rngs.erase(it);
						rngs.insert(news);
					}
				}
			}
			{//新しいrngをいれて、更新クエリを2DSegtreeに投げる
				cerr<<"upd:"<<p.first<<" "<<p.second<<" "<<i<<endl;
				rngs.insert((rng){p.first,p.second,i});
				register_upd(i,p.first,p.second,+1);
			}
			EXAM1();
		}
		for(auto p:querys[i]){//取得クエリを2DSegtreeに投げる
			cerr<<"sum:"<<p.first<<" "<<0<<" "<<p.second+1<<" "<<p.second<<endl;
			register_sum(p.first,N-1,0,p.second+1,p.second);
		}
	}
	vector<ll> fans=seg.solve();
	vector<P> ans;
	for(int i=0;i<fans.size();i++){
		ans.push_back(make_pair(querysid[i],fans[i]));
	}
	sort(all(ans));
	for(auto t:ans)cout<<t.first+1-t.second<<"\n";
}

컴파일 시 표준 에러 (stderr) 메시지

street_lamps.cpp:17:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize("O3")
 
street_lamps.cpp:18:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize("unroll-loops")
 
street_lamps.cpp:19:0: warning: ignoring #pragma gcc target [-Wunknown-pragmas]
 #pragma gcc target("avx2,see4")
 
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:235:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<fans.size();i++){
              ~^~~~~~~~~~~~

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