Submission #1138514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138514		t9unkubj	Aliens (IOI16_aliens)	C++20	0 / 100	1 ms	328 KiB

aliens

#ifdef t9unkubj

#define _GLIBCXX_DEBUG
#include"debug.cpp"
//#include"template_no_debug.h"
#else 
#define dbg(...) 199958
#endif
#include "aliens.h"
#pragma GCC optimize("O3")
using namespace std;
#include"bits/stdc++.h"
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
double pass_time=0;
template<class T,class F>
vector<T>monotone_minima(F&a,int h,int w,int ismax=0){//関数Fに対してminを求める

    vector<T>res(h);
    auto solve=[&](auto&solve,int l,int r,int x,int y)->void{//[x,y) [l,r)について解く
        if(x>=y)return;
        int mid=(x+y)/2;
        pair<T,int>ans=pair<T,int>({(ll)4e18/2+1,4e18},l);
        for(int i=l;i<r;i++){
            ans=min(ans,make_pair(a(mid,i),i));
        }
        solve(solve,l,ans.second+1,x,mid);
        solve(solve,ans.second,r,mid+1,y);
        res[mid]=ans.first;
    };solve(solve,0,w,0,h);

    return res;
}
//
template<class F>
ll monge_d_edge_shortest(F&f,int n,int d,ll inf=2e13){
    ll ac=-inf,wa=inf;
    auto get=[&](ll wj){
        using P=pair<ll,int>;
        vc<P>dp(n,P{1e18,1e9});
        dp[0]={0,0};
        auto dfs=[&](auto&dfs,int l,int r)->void{
            if(l+1==r)return;
            int mid=l+r>>1;
            dfs(dfs,l,mid);
            auto F2=[&](int i,int j)->P{
                i+=mid;
                j+=l;
                return P{f(j,i)+dp[j].first+wj,dp[j].second-1};
            };
            //j to i 
            auto R=monotone_minima<P,decltype(F2)>(F2,r-mid,mid-l,0);
            rep(i,R.size()){
                chmin(dp[i+mid],R[i]);
            }
            dfs(dfs,mid,r);
        };
        dfs(dfs,0,n);
        if(wj==0)dbg(dp);
        return dp.back();
    };
    while(wa-ac>1){
        ll wj=ac+wa>>1;
        if(-get(wj).second>=d)ac=wj;
        else wa=wj;
    }
    return get(ac).first-ac*d;
}

template<class F>
pair<ll,ll> monge_edge_shortest2(F&f,int n){
    auto get=[&](){
        using P=pair<ll,int>;
        vc<P>dp(n,P{1e18,1e9});
        dp[0]={0,0};
        auto dfs=[&](auto&dfs,int l,int r)->void{
            if(l+1==r)return;
            int mid=l+r>>1;
            dfs(dfs,l,mid);
            auto F2=[&](int i,int j)->P{
                i+=mid;
                j+=l;
                return P{f(j,i)+dp[j].first,dp[j].second+1};
            };
            //j to i 
            auto R=monotone_minima<P,decltype(F2)>(F2,r-mid,mid-l,0);
            rep(i,R.size()){
                chmin(dp[i+mid],R[i]);
            }
            dfs(dfs,mid,r);
        };
        dfs(dfs,0,n);
        return dp.back();
    };
    auto res=get();
    return res;
}
using S=pair<int,int>;
S op(S a,S b){
    return max(a,b);
}
struct segtree{
    int n;
    vc<S>node;
    segtree(int n):n(n),node(n*2,{-1e9,-1e9}){}
    void set(int i,S x){
        node[i+=n]=x;
        while(i>>=1)node[i]=op(node[i*2],node[i*2+1]);
    }
    S prod(int l,int r){
        l+=n,r+=n;
        S res={-1e9,-1e9};
        while(l<r){
            if(l&1)res=op(res,node[l++]);
            if(r&1)res=op(res,node[--r]);
            l/=2,r/=2;
        }
        return res;
    }
};
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    set<pair<int,int>>nw;
    rep(i,n){
        if(r[i]-c[i]<0){
            swap(c[i],r[i]);
        }   
        nw.insert({c[i],r[i]});
    }
    
    n=nw.size();
    c=r=vc<int>(n);
    int now=0;
    for(auto&x:nw){
        c[now]=x.first;
        r[now]=x.second;
        now++;
    }

    vc<set<pair<int,int>>>is(m);
    rep(i,n){
        is[r[i]].insert({c[i],i});
    }
    dbg(r,c);
    segtree seg(m);
    auto modify=[&](int i){
        if(is[i].empty())seg.set(i,{-1e9,-1e9});
        else seg.set(i,{(*is[i].rbegin()).first,i});
    };
    rep(i,m){
        modify(i);
    }

    vc<int>used(n);
    rep(i,n){
        if(used[i])continue;
        is[r[i]].erase(pair<int,int>{c[i],i});
        modify(r[i]);
        int l1=c[i];
        int r1=r[i];
        while(1){
            auto it=seg.prod(l1,r1+1);
            if(it.first<c[i])break;
            auto tar=*is[it.second].rbegin();
            used[tar.second]=1;
            is[it.second].erase(tar);
            modify(it.second);
        }
        is[r[i]].insert(pair<int,int>{c[i],i});
        modify(r[i]);
    }

    vc<pair<int,int>>Rs;
    rep(i,n){
        if(!used[i]){
            Rs.push_back({r[i],c[i]});
        }
    }
    sort(all(Rs));
    n=Rs.size();
    r=c=vc<int>(n);
    rep(i,n)tie(r[i],c[i])=Rs[i];
    dbg(r,c);
    ll inf=2e18;
    //i から j へ遷移
    //⇔[i , j-1] を使う
    auto cost=[&](int i,int j)->ll{
        if(j-1<0||i>j-1)return inf;
        int e1=(r[j-1]-c[i]+1);
        ll Cs=(i==0?0:(ll)r[i-1]*r[i-1]);
        return ll(e1)*e1-Cs;
    };
    chmin(k,n);
    auto r1=monge_d_edge_shortest(cost,n+1,k);
    auto r2=monge_edge_shortest2(cost,n+1);
    if(r2.second<=k)chmin(r1,r2.first);
    return r1;
}
void run(){
    int n,m,k;
    cin>>n>>m>>k;
    vc<int>r(n),c(n);
    rep(i,n)cin>>r[i]>>c[i];
    dbg(take_photos(n,m,k,r,c));
}
/*
int main(){
#ifdef t9unkubj
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
    run();
}
*/

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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