Submission #1073756

#TimeUsernameProblemLanguageResultExecution timeMemory
1073756amirhoseinfar1385Aliens (IOI16_aliens)C++17
100 / 100
965 ms32984 KiB
#include "aliens.h" #include<bits/stdc++.h> using namespace std; const long long maxn=100000+10,maxr=1e6+100; long long n,m,k,cost[maxn],inf=1e14; vector<pair<long long,long long>>allv; struct func{ long long x0,y0,sh,w; func(){ y0=inf; sh=0; x0=0; w=0; } long long get(long long x){ return y0+(x-x0)*sh; } }fakefunc; struct lichao{ struct node{ func f; long long cl,cr; node(){ cl=cr=-1; } }fakenode; vector<node>seg; lichao(){ seg.resize(1); } void clear(){ for(long long i=0;i<(long long)seg.size();i++){ seg[i].f=fakefunc; } } long long getl(long long i){ if(seg[i].cl==-1){ seg.push_back(fakenode); seg[i].cl=(long long)seg.size()-1; } return seg[i].cl; } long long getr(long long i){ if(seg[i].cr==-1){ seg.push_back(fakenode); seg[i].cr=(long long)seg.size()-1; } return seg[i].cr; } void upd(long long i,long long l,long long r,func f){ if(l==r){ return ; } long long mid=(l+r)>>1; if(seg[i].f.get(l)>f.get(l)||(seg[i].f.get(l)==f.get(l)&&seg[i].f.w>f.w)){ swap(seg[i].f,f); } if(l==r-1){ return ; } if(seg[i].f.get(mid)>f.get(mid)||(seg[i].f.get(mid)==f.get(mid)&&seg[i].f.w>f.w)){ swap(seg[i].f,f); upd(getl(i),l,mid,f); }else{ upd(getr(i),mid,r,f); } } func pors(long long i,long long l,long long r,long long x){ if(l==r||i==-1){ return fakefunc; } long long mid=(l+r)>>1; func ret; if(x>=mid){ ret=pors(seg[i].cr,mid,r,x); }else{ ret=pors(seg[i].cl,l,mid,x); } if(seg[i].f.get(x)<ret.get(x)||(seg[i].f.get(x)==ret.get(x)&&seg[i].f.w<ret.w)){ ret=seg[i].f; } return ret; } }lich; long long take_photos(int n_,int m_,int k_, std::vector<int> r, std::vector<int> c) { n=n_; m=m_; k=k_; allv.resize(n); for(long long i=0;i<n;i++){ allv[i]=make_pair(r[i],c[i]); if(allv[i].first>allv[i].second){ swap(allv[i].first,allv[i].second); } allv[i].second=-allv[i].second; } sort(allv.begin(),allv.end()); vector<pair<long long,long long>>fake; for(long long i=0;i<n;i++){ allv[i].second*=-1; if(i==0||fake.back().second<allv[i].second){ fake.push_back(allv[i]); } } allv=fake; n=(long long)fake.size(); for(long long i=1;i<n;i++){ long long c=max(-1ll,allv[i-1].second-allv[i].first); c++; c*=c; cost[i]=c; } long long opt=0; long long low=-1,high=1e14,mid; while(high-low>1){ mid=(high+low)>>1; lich.clear(); long long last=0,tedlast=0; for(long long i=0;i<n;i++){ func f; f.x0=0; f.y0=(allv[i].first-1)*(allv[i].first-1)+last+mid-cost[i]; f.sh=-2*(allv[i].first-1); f.w=tedlast+1; lich.upd(0,0,maxr,f); func hehe=lich.pors(0,0,maxr,allv[i].second); last=hehe.get(allv[i].second)+allv[i].second*allv[i].second; tedlast=hehe.w; } if(tedlast<=k){ high=mid; }else{ low=mid; } } mid=high; lich.clear(); long long last=0,tedlast=0; for(long long i=0;i<n;i++){ func f; f.x0=0; f.y0=(allv[i].first-1)*(allv[i].first-1)+last+mid-cost[i]; f.sh=-2*(allv[i].first-1); f.w=tedlast+1; lich.upd(0,0,maxr,f); func hehe=lich.pors(0,0,maxr,allv[i].second); last=hehe.get(allv[i].second)+allv[i].second*allv[i].second; tedlast=hehe.w; // cout<<mid<<" "<<i<<" "<<last<<" "<<tedlast<<endl; } last-=mid*k; //cout<<mid<<endl; return last; }

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:117:15: warning: unused variable 'opt' [-Wunused-variable]
  117 |     long long opt=0;
      |               ^~~
#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...