Submission #926977

#	Time	Username	Problem	Language	Result	Execution time	Memory
926977		MtSaka	Aliens (IOI16_aliens)	C++17	100 / 100	290 ms	6708 KiB

aliens

#include<bits/stdc++.h>
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,n) for(ll i=0;i<(ll)n;++i)
#define rep3(i,l,r) for(ll i=(ll)l;i<(ll)r;++i)
#define rep(...) overload(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)a-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
template<typename T,typename U>inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}
static constexpr ll mod1=998244353;
static constexpr ll mod=1000000007;
static constexpr ll inf=numeric_limits<ll>::max()/2;
using vl=vector<ll>;
struct RMQ{
    private:
    int sz;
    vector<ll>seg;
    public:
    RMQ(int n):sz(1){
        while(sz<n)sz<<=1;
        seg.resize(sz<<1,inf);
    }
    RMQ(const vector<ll>&v):sz(1){
        while(sz<(int)v.size())sz<<=1;
        seg.resize(sz<<1,inf);
        rep(i,v.size())seg[i+sz]=v[i];
        rrep(i,sz)seg[i]=min(seg[i<<1],seg[i<<1^1]);
    }
    ll prod(int l,int r)const{
        l+=sz,r+=sz;
        ll ret=inf;
        while(l!=r){
            if(l&1)chmin(ret,seg[l++]);
            if(r&1)chmin(ret,seg[--r]);
            l>>=1,r>>=1;
        }
        return ret;
    }
};
ll take_photos(int n,int m,int k,vector<int>r,vector<int>c){
    rep(i,n)if(r[i]>c[i])swap(r[i],c[i]);
    vl idx(n);iota(all(idx),0);
    sort(all(idx),[&](ll i,ll j){return (r[i]!=r[j]?r[i]<r[j]:c[i]>c[j]);});
    vector<pair<ll,ll>>v;
    for(auto i:idx){
        if(v.empty()||v.back().second<c[i]){    
            v.emplace_back(r[i],c[i]);
        }
    }
    n=v.size();
    chmin(k,n);
    auto cost=[&](ll i,ll j)->ll {
        if(i==j)return 0;
        if(j==0)return 0;
        return (v[j-1].second-v[i].first+1)*(v[j-1].second-v[i].first+1)-(i>0&&v[i-1].second>=v[i].first?(v[i-1].second-v[i].first+1)*(v[i-1].second-v[i].first+1):0);
    };
    auto f=[&](ll lambda)->pair<ll,ll> {
        vector<pair<ll,ll>>dp(n+1,{inf,inf});
        dp[0]={0,0};
        vl idx(n+1,0);
        auto check=[&](ll l,ll r)->void {
            if(chmin(dp[r],pair<ll,ll>{dp[l].first+cost(l,r)+lambda,dp[l].second+1})){
                idx[r]=l;
            }
        };
        auto rec=[&](auto&&rec,ll l,ll r)->void {
            if(r-l<=1)return;
            ll mid=(l+r)/2;
            rep(i,idx[l],idx[r]+1)check(i,mid);
            rec(rec,l,mid);
            rep(i,l+1,mid+1)check(i,r);
            rec(rec,mid,r);
        };
        check(0,n);
        rec(rec,0,n);
        return dp[n];
    };
    ll ng=-1,ok=(ll)m*m+1;
    while(ok-ng>1){
        ll mid=(ok+ng)/2;
        auto [val,x]=f(mid);
        //cerr<<mid<<" "<<val<<" "<<x<<endl;
        if(x>k)ng=mid;
        else ok=mid;
    }
    auto [val,x]=f(ok);
    return val-k*ok;
}

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