제출 #207898

#제출 시각아이디문제언어결과실행 시간메모리
207898Segtree가로등 (APIO19_street_lamps)C++14
20 / 100
4643 ms49804 KiB
#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){
               ~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...