제출 #731344

#제출 시각아이디문제언어결과실행 시간메모리
731344ogibogi2004휴가 (IOI14_holiday)C++14
0 / 100
235 ms32596 KiB
#include"holiday.h" #include<bits/stdc++.h> using namespace std; const int MAXN=2e5+5e4+6; const int INF=2e9; int att[MAXN]; int low[MAXN],high[MAXN],n1,start1,d1; priority_queue<int> pq; int cur_sum; int fr[MAXN],ansr[MAXN]; int fl[MAXN],ansl[MAXN]; //start1 will be in left int what_to_check[MAXN]; struct node { int cnt_cities; int sum; }; struct segment_tree { node tree[4*MAXN]; void init() { for(int j=0;j<4*MAXN;j++) { tree[j].cnt_cities=0; tree[j].sum=0; } } void update(int l,int r,int idx,int pos,int val) { if(l>pos)return; if(r<pos)return; if(l==r) { tree[idx].cnt_cities=1; tree[idx].sum=val; return; } int mid=(l+r)/2; update(l,mid,idx*2,pos,val); update(mid+1,r,idx*2+1,pos,val); tree[idx].cnt_cities=tree[idx*2].cnt_cities+tree[idx*2+1].cnt_cities; tree[idx].sum=tree[idx*2].sum+tree[idx*2+1].sum; } int query(int l,int r,int idx,int cnt_needed) { if(cnt_needed<0)return -INF; if(cnt_needed==0)return 0; if(cnt_needed>=tree[idx].cnt_cities)return tree[idx].sum; //cout<<l<<" "<<r<<" "<<tree[idx].cnt_cities<<" "<<cnt_needed<<endl; int mid=(l+r)/2; if(tree[idx*2+1].cnt_cities>=cnt_needed)return query(mid+1,r,idx*2+1,cnt_needed); else return tree[idx*2+1].sum+query(l,mid,idx*2,cnt_needed-tree[idx*2+1].cnt_cities); } }tr; int num[MAXN]; int compute_right(int factor) { int max_time=(n1-start1)*factor+(n1-start1); vector<pair<int,int> >intervals; vector<pair<int,int> >new_intervals; intervals.push_back({0,max_time}); for(;intervals.size()>0;) { memset(what_to_check,-1,sizeof(what_to_check)); for(auto xd:intervals) { int mid=(xd.first+xd.second)/2; if(xd.first-1>=0)low[mid]=ansr[xd.first-1]; else low[mid]=start1; if(xd.second+1<=max_time)high[mid]=ansr[xd.second+1]; else high[mid]=n1; for(int j=low[mid];j<=high[mid];j++) { what_to_check[j]=mid; } } tr.init(); for(int i=start1;i<=n1;i++) { if(i!=start1)tr.update(1,n1,1,num[i],att[i]); int time1=what_to_check[i]; if(time1==-1)continue; int gg=tr.query(1,n1,1,time1-(i-start1)*factor); if(gg>fr[time1]) { fr[time1]=gg; ansr[time1]=i; } } new_intervals.clear(); for(auto xd:intervals) { int mid=(xd.first+xd.second)/2; if(xd.first==xd.second)continue; if(xd.first<=mid-1)new_intervals.push_back({xd.first,mid-1}); if(mid+1<=xd.second)new_intervals.push_back({mid+1,xd.second}); } intervals=new_intervals; } } int compute_left(int factor) { int max_time=(start1-1)*factor+start1; vector<pair<int,int> >intervals; vector<pair<int,int> >new_intervals; intervals.push_back({0,max_time}); for(;intervals.size()>0;) { memset(what_to_check,-1,sizeof(what_to_check)); for(auto xd:intervals) { int mid=(xd.first+xd.second)/2; if(xd.first-1>=0)low[mid]=ansl[xd.second+1]; else low[mid]=1; if(xd.second+1<=max_time)high[mid]=ansl[xd.first-1]; else high[mid]=start1; for(int j=low[mid];j<=high[mid];j++) { what_to_check[j]=mid; } } tr.init(); for(int i=start1;i>=1;i--) { tr.update(1,n1,1,num[i],att[i]); int time1=what_to_check[i]; if(time1==-1)continue; //cout<<"%% "<<i<<" "<<time1<<endl; //cout<<time1-(start1-i)*factor<<endl; int gg=tr.query(1,n1,1,time1-(start1-i)*factor); if(gg>fl[time1]) { fl[time1]=gg; ansl[time1]=i; } } new_intervals.clear(); for(auto xd:intervals) { int mid=(xd.first+xd.second)/2; //cout<<"^^ "<<mid<<" "<<fl[mid]<<" "<<ansl[mid]<<endl; if(xd.first==xd.second)continue; if(xd.first<=mid-1)new_intervals.push_back({xd.first,mid-1}); if(mid+1<=xd.second)new_intervals.push_back({mid+1,xd.second}); } intervals=new_intervals; } } int solve_right() { memset(fl,-1,sizeof(fl)); memset(fr,-1,sizeof(fr)); compute_right(2); compute_left(1); int ret=0; for(int t1=0;t1<MAXN;t1++) { if(fl[t1]<0)continue; if(fr[d1-t1]<0)continue; ret=max(ret,fl[t1]+fr[d1-t1]); //cout<<t1<<" "<<fl[t1]<<" "<<fr[d1-t1]<<endl; } return ret; } int solve_left() { memset(fl,-1,sizeof(fl)); memset(fr,-1,sizeof(fr)); compute_right(1); compute_left(2); int ret=0; for(int t1=0;t1<MAXN;t1++) { if(fr[t1]<0)continue; if(fl[d1-t1]<0)continue; ret=max(ret,fr[t1]+fl[d1-t1]); } return ret; } long long int findMaxAttraction(int n, int start, int d, int attraction[]) { vector<pair<int,int> >by_value; for(int i=0;i<n;i++) { att[i+1]=attraction[i]; by_value.push_back({att[i+1],i+1}); } sort(by_value.begin(),by_value.end()); for(int i=0;i<by_value.size();i++) { num[by_value[i].second]=i+1; } n1=n;start1=start;d1=d; start1++; return max(solve_left(), solve_right()); }

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

holiday.cpp: In function 'int compute_right(int)':
holiday.cpp:102:1: warning: no return statement in function returning non-void [-Wreturn-type]
  102 | }
      | ^
holiday.cpp: In function 'int compute_left(int)':
holiday.cpp:150:1: warning: no return statement in function returning non-void [-Wreturn-type]
  150 | }
      | ^
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:190:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  190 |     for(int i=0;i<by_value.size();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...