Submission #1073750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073750		amirhoseinfar1385	Aliens (IOI16_aliens)	C++17	4 / 100	1 ms	2648 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10,maxk=100+10,maxr=1e6+100;
long long dp[maxn][maxk],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;
      |               ^~~

• Subtask 1: 4 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40