This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |