Submission #67058

#	Time	Username	Problem	Language	Result	Execution time	Memory
67058		moonrabbit2	Aliens (IOI16_aliens)	C++17	100 / 100	1524 ms	204224 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define N 100005
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
int n,m;
stack<P> sstk;
P aa[N],a[N];
ll dp[N],use[N][2],d[N],l;
ll res[N];
ll cmax;int lv,rv;
struct line
{
    ll a,b;
    int mn,mx;
    line(ll aa,ll bb){
        a=aa;
        b=bb;
        mn=mx=0;
    }
    line(ll aa,ll bb,int m1,int m2){
        a=aa;
        b=bb;
        mn=m1;
        mx=m2;
    }
    line(){a=b=mn=mx=0;}
    ll get(ll x){return a*x+b;}
};
struct node
{
    line a;
    node *l=nullptr,*r=nullptr;
    node(ll aa,ll bb){
        a.a=aa;
        a.b=bb;
    }
    node(line x){
        a=x;
    }
    ll get(ll x){return a.get(x);}
};
struct lichao
{
    node *root=nullptr;
    ll query(ll x){return query(root,1,1e6,x);}
    ll query(node *nd,ll l,ll r,ll x){
        if(nd==nullptr) return 1e15;
        ll res=nd->get(x);
        if(cmax>res){
            lv=nd->a.mn;
            rv=nd->a.mx;
            cmax=res;
        }
        else if(cmax==res){
            lv=min(lv,nd->a.mn);
            rv=max(rv,nd->a.mx);
        }
        if(l==r) return res;
        ll m=(l+r)/2;
        if(x<=m&&nd->l!=nullptr)
            return min(res,query(nd->l,l,m,x));
        if(x>m&&nd->r!=nullptr)
            return min(res,query(nd->r,m+1,r,x));
        return res;
    }
    void update(ll a,ll b,int mn,int mx){line ln=line(a,b,mn,mx);update(root,1,1e6,ln);}
    typedef node* pnd;
    void update(pnd &nd,ll l,ll r,line &a){
        if(nd==nullptr){
            nd=new node(a);
            return;
        }
        if(nd->get(l)<a.get(l)&&nd->get(r)<a.get(r)) return;
        if(nd->get(l)>a.get(l)&&nd->get(r)>a.get(r)){
            nd->a=a;
            return;
        }
        ll m=(l+r)/2;
        if(nd->get(m)>a.get(m))
            swap(nd->a,a);
        if(nd->get(l)<a.get(l))
            update(nd->r,m+1,r,a);
        else
            update(nd->l,l,m,a);
    }
};
void solve(ll lambda)
{
    for(int i=0;i<n;i++)
        dp[i]=use[i][0]=use[i][1]=0;
    lichao lc;
    for(int i=0;i<n;i++){
        dp[i]=(a[0].x-a[i].y-1)*(a[0].x-a[i].y-1)+lambda;
        lv=rv=0;
        cmax=dp[i]-a[i].y*a[i].y-2*a[i].y-1-lambda;
        if(i>0){
            ll newv=lc.query(a[i].y)+a[i].y*a[i].y+2*a[i].y+1+lambda;
            if(newv<dp[i])
                dp[i]=newv;
        }
        lv++;rv++;
        use[i][0]=lv;
        use[i][1]=rv;
        lc.update(-2LL*a[i+1].x,dp[i]+d[i]+a[i+1].x*a[i+1].x-2LL*a[i+1].x,lv,rv);
    }
}
ll take_photos(int n_,int m_,int k_,vector<int> r,vector<int> c)
{
    n=n_;m=m_;l=k_;
    for(int i=0;i<n;i++)
        aa[i]=P(min(r[i],c[i]),max(r[i],c[i]));
    sort(aa,aa+n);
    for(int i=0;i<n;i++){
        while(sstk.size()&&sstk.top().x==aa[i].x)
            sstk.pop();
        if(sstk.size()&&sstk.top().y<=aa[i].y)
            sstk.push(aa[i]);
        else if(!sstk.size())
            sstk.push(aa[i]);
    }
    n=0;
    while(sstk.size()){
        a[n++]=sstk.top();
        sstk.pop();
    }
    sort(a,a+n);
    for(int i=0;i<n;i++){
        if(i<n-1&&a[i].y>=a[i+1].x)
            d[i]=-(ll)(a[i].y-a[i+1].x+1)*(ll)(a[i].y-a[i+1].x+1);
    }
    ll L=-(ll)m*m*1000,R=-L,ans=1e18;
    while(L<=R){
        ll M=(L+R)/2;
        solve(M);
        if(use[n-1][1]>=l&&use[n-1][0]<=l)
            return dp[n-1]-M*l;
        if(use[n-1][1]<=l){
            R=M-1;
            ans=min(ans,dp[n-1]-M*use[n-1][1]);
        }
        else
            L=M+1;
    }
    return ans;
}

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