제출 #899481

#제출 시각아이디문제언어결과실행 시간메모리
899481JakobZorzAliens (IOI16_aliens)C++17
100 / 100
969 ms202120 KiB
#include"aliens.h" #include<iostream> #include<algorithm> using namespace std; typedef long long ll; struct Line{ ll a,b; int min_pics,max_pics; }; ll eval(Line l,ll x){ return l.a*x+l.b; } struct CHT{ int l,r; CHT*ch1,*ch2; Line cl; CHT(int l,int r):l(l),r(r),ch1(nullptr),ch2(nullptr){ cl.a=0; cl.b=1e18; } void add(Line line){ int mid=(l+r)/2; if(eval(line,mid)<eval(cl,mid)) swap(line,cl); if(eval(line,mid)==eval(cl,mid)&&eval(line,l)==eval(cl,l)){ cl.min_pics=min(cl.min_pics,line.min_pics); cl.max_pics=max(cl.max_pics,line.max_pics); return; } if(l<r-1){ if(eval(line,l)<eval(cl,l)){ if(ch1==nullptr) ch1=new CHT(l,mid); ch1->add(line); } if(eval(line,r)<eval(cl,r)){ if(ch2==nullptr) ch2=new CHT(mid,r); ch2->add(line); } } } pair<ll,pair<int,int>>get(ll x){ int mid=(l+r)/2; pair<ll,pair<int,int>>res={eval(cl,x),{cl.min_pics,cl.max_pics}}; if(x>=mid&&ch2){ auto res2=ch2->get(x); if(res2.first<res.first){ res=res2; }else if(res2.first==res.first){ res.second.first=min(res.second.first,res2.second.first); res.second.second=max(res.second.second,res2.second.second); } } if(x<mid&&ch1){ auto res2=ch1->get(x); if(res2.first<res.first){ res=res2; }else if(res2.first==res.first){ res.second.first=min(res.second.first,res2.second.first); res.second.second=max(res.second.second,res2.second.second); } } return res; } }; int n; vector<ll>l,r; ll sq(ll x){ return x*x; } bool cmp(pair<int,int>a,pair<int,int>b){ if(a.first==b.first) return a.second>b.second; return a.first<b.first; } // (points, num of pictures) if pictures are unlimited but have a specific cost // num of picures will be minimal and maximal while still having optimal points pair<ll,pair<int,int>>get(ll cost){ vector<ll>dp(n+1); // optimum for first i intervals vector<pair<int,int>>num_pic(n+1); CHT cht(0,1<<20); for(int i=1;i<=n;i++){ Line line; line.b=l[i-1]*l[i-1]+dp[i-1]+cost; if(i!=1) line.b-=sq(max(0LL,r[i-2]-l[i-1])); line.a=-2*l[i-1]; line.min_pics=num_pic[i-1].first+1; line.max_pics=num_pic[i-1].second+1; cht.add(line); auto res=cht.get(r[i-1]); res.first+=r[i-1]*r[i-1]; dp[i]=res.first; num_pic[i]=res.second; //cout<<"res1 "<<dp[i]<<" "<<num_pic[i].first<<" "<<num_pic[i].second<<endl; /*dp[i]=1e18; for(int j=0;j<i;j++){ ll curr=r[i-1]*r[i-1]-2*l[j]*r[i-1]+l[j]*l[j]; curr+=dp[j]; curr+=cost; if(j) curr-=sq(max(0LL,r[j-1]-l[j])); if(curr<dp[i]){ dp[i]=curr; num_pic[i].first=num_pic[j].first+1; num_pic[i].second=num_pic[j].second+1; }else if(curr==dp[i]){ num_pic[i].first=min(num_pic[i].first,num_pic[j].first+1); num_pic[i].second=max(num_pic[i].second,num_pic[j].second+1); } }*/ //cout<<"res2 "<<dp[i]<<" "<<num_pic[i].first<<" "<<num_pic[i].second<<endl; //cout<<"\n"; } return{dp[n],num_pic[n]}; } ll take_photos(int N,int m,int k,vector<int>R,vector<int>C){ n=N; vector<pair<int,int>>intervals_sorted; for(int i=0;i<n;i++){ if(R[i]>C[i]) swap(R[i],C[i]); intervals_sorted.emplace_back(R[i],C[i]); } sort(intervals_sorted.begin(),intervals_sorted.end(),cmp); int right_done=-1; for(auto i:intervals_sorted){ if(i.second>right_done){ l.push_back(i.first); r.push_back(i.second+1); right_done=i.second; } } n=(int)l.size(); k=min(n,k); ll l=0,r=(ll)m*m+1; ll opt; while(true){ ll mid=(l+r)/2; auto res=get(mid); //cout<<mid<<": "<<res.first<<" "<<res.second.first<<" "<<res.second.second<<endl; if(res.second.first>k) l=mid; if(res.second.second<k) r=mid; if(res.second.first<=k&&k<=res.second.second){ opt=mid; break; } } //cout<<"opt "<<opt<<"\n"; auto res=get(opt); ll ret=res.first-opt*k; return ret; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...