Submission #1138530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138530		t9unkubj	Aliens (IOI16_aliens)	C++20	Compilation error	0 ms	0 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 coef=ismax?-1:1;
        int mid=(x+y)/2;
        pair<T,int>ans=make_pair(numeric_limits<T>::max()/2+1,l);
        for(int i=l;i<r;i++){
            ans=min(ans,make_pair(a(mid,i)*coef,i));
        }
        solve(solve,l,ans.second+1, x,mid);
        solve(solve,ans.second,r, mid+1,y);
        res[mid]=ans.first*coef;
    };solve(solve,0,w,0,h);
    return res;
}

//
template<class F>
pair<ll,int> monge_edge_solver(F&f,int n,int need_cnt=1,ll pena=0){
    vc<ll>dp(n,(ll)1e18);
    dp[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)->ll{
            i+=mid;
            j+=l;
            return f(j,i)+dp[j]+pena;
        };
            //j to i 
        auto R=monotone_minima<ll,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(need_cnt){
        return pair<ll,int>{dp.back(),monge_edge_solver(f,n,0,pena+1).first-dp.back()};
    }
    return {dp.back(),0};
}
template<class F>
ll monge_d_edge_shortest(F&f,int n,int d,ll inf=2e13){
    ll ac=-inf,wa=inf;
    while(wa-ac>1){
        ll wj=ac+wa>>1;
        if(monge_edge_solver(f,n,1,wj).second>=d)ac=wj;
        else wa=wj;
    }
    return monge_edge_solver(f,n,0,ac).first-ac*d;
}

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 dec=[&](int i){
        if(i==0)return 0ll;
        ll r1=r[i-1];
        ll c1=c[i];
        return max(0ll,r1-c1+1)*max(0ll,r1-c1+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 ans=ll(e1)*e1-dec(i);
        return ans;
    };
    chmin(k,n);
    auto r1=monge_d_edge_shortest(cost,n+1,k);
    auto r2=monge_edge_solver(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
      |         ^~~~
/usr/bin/ld: /tmp/ccD75faJ.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccDJv0xs.o:aliens.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status