| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1083330 | vjudge1 | Aliens (IOI16_aliens) | C++17 | 0 ms | 0 KiB |
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<bits/stdc++.h>
#define cir(i,a,b) for(int i=a;i<b;++i)
using namespace std;
using lint=long long;
using lf=long double;
// function: f(x)=kx+b
class line{
private:
lf k,b;int id;
public:
constexpr auto operator()(lf x) const{
return pair(k*x+b,-id);
}
line(auto _k=1e12,auto _b=1e12,int _id=0):k(_k),b(_b),id(_id){}
};
class segment{
private:
vector<line> a;
constexpr auto ls(int u){return u*2;}
constexpr auto rs(int u){return u*2+1;}
auto insert(int u,int l,int r,line f){
const auto g=a[u];
if(f(l)>g(l)&&f(r)>g(r)) return;
if(f(l)<g(l)&&f(r)<g(r)) return a[u]=f,void();
if(l==r) return;
const auto mid=(l+r)/2;
if(f(mid)<g(mid)){
a[u]=f;
if(f(l)>g(l)) insert(ls(u),l,mid,g);
else insert(rs(u),mid+1,r,g);
}else{
if(f(l)>g(l)) insert(rs(u),mid+1,r,f);
else insert(ls(u),l,mid,f);
}
}
auto query(int u,int l,int r,int p){
if(l==r) return a[u](p);
const auto mid=(l+r)/2;
return min(a[u](p),p-1<mid?query(ls(u),l,mid,p):query(rs(u),mid+1,r,p));
}
int n;
public:
auto insert(line f){insert(1,0,n-1,f);}
auto query(int p){return query(1,0,n-1,p);}
segment(int _n):n(_n),a(_n<<2,line(1e12,1e12,0)){}
};
struct seg{lint l,r;};
int main(){
ios::sync_with_stdio(false),cin.tie(0);
int n,m,k;cin>>n>>m>>k;
vector<seg> a(n);
for(auto&[l,r]:a){
lint x,y;cin>>x>>y;
tie(l,r)=minmax(x,y);
}
sort(a.begin(),a.end(),[](auto&a,auto&b){
return a.l==b.l?a.r>b.r:a.l<b.l;
});
constexpr auto sqr=[&](auto x){return x*x;};
[&](){
const auto na=a;
auto cmxr=-1;
a.clear();
for(auto&[l,r]:na){
if(r<cmxr+1) continue;
a.emplace_back(l,(cmxr=r));
}
n=a.size();
}();
auto l=-1e12l,r=1e12l,ans=-1.0l;
cir(i,0,60){
const auto mid=(l+r)/2;
const auto[w,c]=[&](){
vector<lf> f(n),c(n);
segment sg(m+7);
sg.insert(line(-a[0].l*2,sqr(a[0].l),0));
cir(i,0,n){
const auto[fx,cnt]=sg.query(a[i].r+1);
f[i]=fx+sqr(a[i].r+1)+mid;
c[i]=-cnt+1;
if(i+1<n) sg.insert(line(-a[i+1].l*2,f[i]-sqr(max(a[i].r-a[i+1].l+1,0ll))+sqr(a[i+1].l),cnt+1));
}
return pair(f[n-1],c[n-1]);
}();
ans=w-min<lint>(c,k)*mid;
c>k-1?(r=mid):(l=mid);
}
cout<<(lint)(round(ans))<<'\n';
return 0;
}