제출 #207898

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
207898		Segtree	가로등 (APIO19_street_lamps)	C++14	20 / 100	4643 ms	49804 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;
#define rep(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 all(x) x.begin(),x.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("unroll-loops")
#pragma gcc target("avx2,see4")

#define N 300010
namespace seg{
	ll dat[2*N];
	void init(){
		rep(i,2*N)dat[i]=0;
	}
	void add(ll i,ll x){
		if(i<0)return;
		i+=N;
		for(;i;i>>=1)dat[i]+=x;
	}
	ll sum(ll l,ll r){
		l+=N,r+=N+1;
		ll res=0;
		for(ll a=l,b=r;a<b;a>>=1,b>>=1){
			if(a&1)res+=dat[a++];
			if(b&1)res+=dat[--b];
		}
		return res;
	}
}
typedef struct range{
	ll l,r,val;
	bool operator<(const range&key)const{
		return this->l<key.l;
	}
}range;
namespace DS{
	set<range> S;
	void init(){
		seg::init();
		S.clear();
	}
	set<range>::iterator erase(set<range>::iterator it){
		if(it==S.end())return it;
		seg::add(it->val,-(it->r-it->l+1));
		return S.erase(it);
	}
	void ins(ll l,ll r,ll val){
		if(l>r)return;
		seg::add(val,r-l+1);
		S.insert((range){l,r,val});
	}
	void insert(ll l,ll r,ll val){
		//cerr<<"beg_sum:"<<seg::sum(0,N-1)<<endl;
		range x=(range){l,r,val};
		{//[l,r]に完全に含まれているものを消す
			auto it=S.lower_bound(x);
			while(1){
				if(it==S.end())break;
				if(r<it->r)break;
				it=erase(it);
			}
		}
		bool done=0;
		{//[l,r]を完全に含んでいるものがある場合
			auto it=S.upper_bound(x);
			if(it!=S.begin()){
				it--;
				if(it->l<=l&&r<=it->r){
					ll itl=it->l,itr=it->r,itval=it->val;
					erase(it);
					ins(itl,l-1,itval);
					ins(r+1,itr,itval);
					done=1;
					ll sum=0;
					for(auto e:S)sum+=e.r-e.l+1;
				}
			}
		}
		if(done==0){//そうでない場合
			{//右側で交差しているもの
				auto it=S.upper_bound(x);
				if(it!=S.end()){
					ll itl=it->l,itr=it->r,itval=it->val;
					erase(it);
					ins(r+1,itr,itval);
				}
			}
			{//左側で交差しているもの
				auto it=S.lower_bound(x);
				if(it!=S.begin()){
					it--;
					ll itl=it->l,itr=it->r,itval=it->val;
					erase(it);
					ins(itl,l-1,itval);
				}
			}
		}
		//cerr<<"add:"<<l<<" "<<r<<" "<<val<<endl;
		seg::add(val,r-l+1);
		S.insert((range){l,r,val});
		//cerr<<"seg_sum:"<<seg::sum(0,N-1)<<endl;
	}
};
ll n,q;
string s;
vector<ll> upd[N];
typedef struct query{
	ll a,b,id;
}query;
vector<query> qrys[N];
ll fans[N];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cin>>n>>q;
	//n=Data::n,q=Data::q;
	cin>>s;
	//s=Data::s;
	rep(i,n){
		if(s[i]=='0')upd[i].push_back(0);
	}
	bool fi=1;
	ll toggles=0;
	ll rui[N];
	for(int t=1;t<=q;t++){
		string typ;
		cin>>typ;
		//typ=Data::typ[t-1];
		if(typ=="toggle"){
			ll x;
			cin>>x;
			//x=Data::x[t-1];
			x--;
			if(s[x]=='0'){
				upd[x].push_back(t);
				s[x]='1';
			}
			else{
				upd[x].push_back(t);
				s[x]='0';
			}
			toggles=t;
		}
		if(typ=="query"){
			if(fi){
				rep(i,n)if(s[i]=='0')upd[i].push_back(t);
				rui[0]=0;
				for(int i=0;i<n;i++)rui[i+1]=rui[i]+(s[i]-'0');
				fi=0;
			}
			ll a,b;
			cin>>a>>b;
			//a=Data::a[t-1],b=Data::b[t-1];
			a--,b--;
			fans[t]=(rui[b]-rui[a]==b-a)*(t-1-toggles);
			qrys[b-1].push_back((query){a,b-1,t});
		}
	}
	DS::init();
	DS::ins(0,toggles,-1);
	for(int b=0;b<n;b++){
		for(int i=0;i+1<upd[b].size();i+=2){
			ll l=upd[b][i],r=upd[b][i+1]-1;
			DS::insert(l,r,b);
			//cerr<<"upd:"<<l<<" "<<r<<" "<<b<<endl;
		}
		for(query qry:qrys[b]){
			//cerr<<"qry:"<<qry.a<<" "<<qry.b<<" "<<qry.id<<endl;
			fans[qry.id]+=toggles+1-seg::sum(qry.a,qry.b);
		}
	}
	for(int i=toggles+1;i<=q;i++){
		cout<<fans[i]<<"\n";
		//FANS.push_back(fans[i]);
	}
}

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

street_lamps.cpp:14:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize("O3")
 
street_lamps.cpp:15:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize("unroll-loops")
 
street_lamps.cpp:16:0: warning: ignoring #pragma gcc target [-Wunknown-pragmas]
 #pragma gcc target("avx2,see4")
 
street_lamps.cpp: In function 'void DS::insert(ll, ll, ll)':
street_lamps.cpp:92:9: warning: unused variable 'itl' [-Wunused-variable]
      ll itl=it->l,itr=it->r,itval=it->val;
         ^~~
street_lamps.cpp:101:19: warning: unused variable 'itr' [-Wunused-variable]
      ll itl=it->l,itr=it->r,itval=it->val;
                   ^~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:172:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i+1<upd[b].size();i+=2){
               ~~~^~~~~~~~~~~~~~

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