제출 #971907

#제출 시각아이디문제언어결과실행 시간메모리
971907Warinchai휴가 (IOI14_holiday)C++14
24 / 100
220 ms23808 KiB
#include"holiday.h" #include<bits/stdc++.h> //#define int long long using namespace std; long long rvid[100005]; struct segtree{ long long info[400005]; long long freq[400005]; void upd(int st,int en,int i,int pos,int val){ if(st>pos||en<pos)return; //cerr<<"range:"<<st<<" "<<en<<"\n"; if(st==en)return info[i]+=val,freq[i]++,void(); int m=(st+en)/2; upd(st,m,i*2,pos,val); upd(m+1,en,i*2+1,pos,val); info[i]=info[i*2]+info[i*2+1]; freq[i]=freq[i*2]+freq[i*2+1]; } void un_upd(int st,int en,int i,int pos,int val){ if(st>pos||en<pos)return; if(st==en)return info[i]-=val,freq[i]-=1,void(); int m=(st+en)/2; un_upd(st,m,i*2,pos,val); un_upd(m+1,en,i*2+1,pos,val); info[i]=info[i*2]+info[i*2+1]; freq[i]=freq[i*2]+freq[i*2+1]; } long long fans(int st,int en,int i,long long pos){ //cerr<<"Range:"<<st<<" "<<en<<"\n"; if(st==en)return min(freq[i],pos)*(rvid[st]); int m=(st+en)/2; if(pos<=freq[i*2+1])return fans(m+1,en,i*2+1,pos); else return fans(st,m,i*2,pos-freq[i*2+1])+info[i*2+1]; } void reset(int st,int en,int i){ info[i]=0; freq[i]=0; if(st==en)return; int m=(st+en)/2; reset(st,m,i*2); reset(m+1,en,i*2+1); } }tr; vector<long long>v; int id[100005]; long long dpl[100005]; long long dpr[100005]; int optl[100005]; int optr[100005]; map<int,int>mp; struct query{ int st,en,optl,optr; query(int a,int b,int c,int d){ st=a,en=b,optl=c,optr=d; } }; long long findMaxAttraction(int n, int start, int d, int attraction[]) { for(int i=0;i<n;i++)if(!mp[attraction[i]])v.push_back(attraction[i]),mp[attraction[i]]++; v.push_back(0); sort(v.begin(),v.end()); for(int i=0;i<v.size();i++)rvid[i+1]=v[i]; for(int i=0;i<n+1;i++)id[i]=lower_bound(v.begin(),v.end(),attraction[i])-v.begin()+1; long long ans=0; int cur=start; queue<pair<int,query>>q; q.push({1,query(0,d,start,n-1)}); int cnt=0; int curlv=1; //cerr<<"work\n"; while(!q.empty()){ auto x=q.front().second; int lv=q.front().first; q.pop(); if(x.st>x.en)continue; int m=(x.st+x.en)/2; //cerr<<"cur:"<<cur<<"\n"; if(curlv<lv){ curlv++; //cerr<<"reset\n"; cnt+=n; tr.reset(1,n+1,1); cur=start; } //cerr<<x.optl<<" "<<x.optr<<"\n"; while(cur<x.optl){ cnt++; tr.upd(1,n+1,1,id[cur],attraction[cur]); cur++; } pair<long long,int>opt={-1ll,-1}; for(int i=x.optl;i<=x.optr;i++){ if(cur==i){ cnt++; tr.upd(1,n+1,1,id[cur],attraction[cur]); cur++; } int left=m-abs(start-i); long long x=tr.fans(1,n+1,1,left); opt=max(opt,{x,i}); } dpr[m]=opt.first; optr[m]=opt.second; //cerr<<x.st<<" "<<x.en<<" "<<m<<" "<<opt.first<<" "<<opt.second<<"\n"; q.push({lv+1,query(x.st,m-1,x.optl,opt.second)}); q.push({lv+1,query(m+1,x.en,opt.second,x.optr)}); } //cerr<<"count:"<<cnt<<"\n"; //cerr<<"work\n"; //for(int i=0;i<=d;i++)cerr<<dpr[i]<<" "; //cerr<<"\n"; tr.reset(1,n+1,1); cur=start; q.push({1,query(0,d,0,start)}); //cerr<<"work\n"; attraction[start]=0; id[start]=1; cnt=0; curlv=1; while(!q.empty()){ auto x=q.front().second; int lv=q.front().first; q.pop(); if(x.st>x.en)continue; int m=(x.st+x.en)/2; if(curlv<lv){ curlv++; //cerr<<"reset\n"; cnt+=n; tr.reset(1,n+1,1); cur=start; } //cerr<<x.optr<<" "<<x.optl<<"\n"; while(cur>x.optr){ cnt++; tr.upd(1,n+1,1,id[cur],attraction[cur]); cur--; } //cerr<<"cur:"<<cur<<"\n"; pair<long long,int>opt={-1ll,-1}; for(int i=x.optr;i>=x.optl;i--){ if(cur==i){ cnt++; tr.upd(1,n+1,1,id[cur],attraction[cur]); cur--; } int left=m-abs(start-i); long long x=tr.fans(1,n+1,1,left); opt=max(opt,{x,i}); } dpl[m]=opt.first; optl[m]=opt.second; //cerr<<x.st<<" "<<x.en<<" "<<m<<" "<<opt.first<<" "<<opt.second<<" "<<x.optl<<" "<<x.optr<<"\n"; q.push({lv+1,query(x.st,m-1,opt.second,x.optr)}); q.push({lv+1,query(m+1,x.en,x.optl,opt.second)}); } //cerr<<"count:"<<cnt<<"\n"; //for(int i=0;i<=d;i++)cerr<<dpl[i]<<" "; //cerr<<"\n"; for(int i=0;i<=d;i++){ int left=d-i-abs(optr[i]-start); if(left<0)break; //cerr<<i<<" "<<left<<" "<<optr[i]<<" "<<dpr[i]+dpl[left]<<"\n"; ans=max(ans,dpr[i]+dpl[left]); } for(int i=0;i<=d/2;i++){ int left=d-i-abs(optl[i]-start); if(left<0)break; ans=max(ans,dpl[i]+dpr[left]); } return ans; }

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

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:61:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i=0;i<v.size();i++)rvid[i+1]=v[i];
      |                 ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...