Submission #837773

#	Time	Username	Problem	Language	Result	Execution time	Memory
837773		ballbattle	Aliens (IOI16_aliens)	C++14	25 / 100	99 ms	32572 KiB

aliens

#include "aliens.h"

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long ll;
typedef long double f;

typedef pair<ll,ll> pll;
typedef pair<f,ll> pfl;

typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<pfl> vp;
typedef vector<int> vi;

struct line {
    f c;
    f slope;
    pfl operator()(ll x) {return make_pair(c + ((f)x)*slope, my_k);}
    ll my_k;
};
struct node {
    line* best;
    node* lc;
    node* rc;
};
typedef vector<line*> vl;

#define rep(a,b,c) for(ll a = b; a < c; a++)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define all(a) a.begin(),a.end()
#define sz(a) a.size()

pfl operator+ (pfl a, pfl b) {return mp(a.first+b.first,a.second+b.second);}

pfl _dp(f lambda);
void build(node*v, ll l, ll r);
void insert(node*v, line*seg, ll l, ll r);
pfl query(node*v, ll x, ll l, ll r);

ll n;
ll k;

vpll p;
vll h;

vp dp;

node* tree;
line inf;
vl lines;

long long take_photos(int N, int M, int K, vi R, vi C) {
    k = K;
    p.clear();
    rep(i,0,N) {if (R[i] > C[i]) {swap(R[i],C[i]);}} // Flip over diagonal
    rep(i,0,N) {p.pb(mp(C[i],-R[i]));}
    sort(all(p)); // Sort in a way that makes worse points come before better points
    rep(i,0,N) {
        C[i] = p[i].first;
        R[i] = -p[i].second;
    }
    /*cout << "C[i] R[i]" << endl;
    rep(i,0,N) {cout << C[i] << " " << R[i] << endl;}*/
    // C[i] is in increasing order
    // R[i] is in decreasing order
    // The first point is the optimal

    p.clear();
    p.pb(mp(-1,-1)); // thing....
    rep(i,0,N) {

        while ((C[i] >= p[sz(p)-1].first) && (R[i] <= p[sz(p)-1].second)) { // Prune bad points
            p.pop_back();
        }
        p.pb(mp(C[i],R[i])); // Add points in (x,-y) format to p
    }
    
    /*cout << "points:" << endl;
    rep(i,0,sz(p)) {cout << p[i].first << " " << p[i].second << endl;}*/

    n = sz(p);
    h.resize(n,0);
    rep(i,0,n-1) {h[i] = p[i].first - p[i+1].second;}

    // Prepare Li Chao tree
    inf.c = f(100000000);
    inf.slope = f(0);

    /*cout << "h:" << endl;
    rep(i,0,n) {cout << h[i] << " ";}
    cout << endl;*/

    /*rep(i,0,10) {cout << _dp(f(i)).first << endl;}*/

    ll ans = 1000000000000;

    f lo = f(0.0);
    f hi = f(10000000001);
    f mid;
    pfl curr;
    rep(i,0,64) {
        mid = (lo)/f(2) + (hi)/f(2);
        //cout << mid << endl;
        curr = _dp(mid);
        //cout << curr.first << " " << curr.second << " " << mid << endl; 
        if (curr.second == min(k,n-1)) {
            ans = round(curr.first - mid*(f(curr.second)));
            break;
        } else if (curr.second > min(k,n-1)) {
            lo = mid;
        } else {
            hi = mid;
            /*ll tmp = round(curr.first - mid*(f(curr.second))); // Hotfix
            ans = min(tmp, ans);*/
        }
    }
    if (ans == 1000000000000) {ans = round(curr.first - mid*(f(k)));} // Based solution
    //if (ans==-1) {ans = round(curr.first - mid*(f(curr.second)));}

    //cout << n-1 << endl;
    return ans;
}

pfl _dp(f lambda) {
    tree = nullptr; // O(n) bc this litterally deletes the previous tree
    lines.clear();
    // Initialize the Li Chao Tree
    tree = new node;
    build(tree, 0, n); // Include dummy p[0] bc we need it in the dp
    
    dp.clear();
    dp.resize(n,mp(f(10000000000000000),0));
    //dp[0] = mp(f( (p[0].first-p[0].second+1)*(p[0].first-p[0].second+1) ),1);
    dp[0] = mp(f(0),0);
    //cout << "built xd" << endl;
    rep(i,0,n) {
        /*rep(j,0,i) {
            ll x_i = p[i].first;
            ll x_j = p[j].first;
            if (h[j] < 0) {
                dp[i] = min(dp[i], dp[j] + mp(f( (x_i-x_j+h[j]+1)*(x_i-x_j+h[j]+1) ),1) + mp(lambda,0));
            } else {
                dp[i] = min(dp[i], dp[j] + mp(f( (x_i-x_j+h[j]+1)*(x_i-x_j+h[j]+1) - (h[j]+1)*(h[j]+1) ),1) + mp(lambda,0));
            }
        }*/
        f x = (f)p[i].first;
        if (i!=0) dp[i] = mp(x*x,0) + query(tree, i, 0, n) + mp(lambda,1); // wtf based
        //cout << "i: " << i << " " << dp[i].first << " " << dp[i].second << endl;

        lines.pb(nullptr);
        lines[i] = new line;
        lines[i]->my_k = dp[i].second; // include k xd
        if (h[i] < 0) {
            lines[i]->c = dp[i].first + x*x + (f)((h[i]+1)*(h[i]+1)) - 2*x*(f)(h[i]+1);
            lines[i]->slope = (f)(-2*(x-h[i]-1));
        } else {
            lines[i]->c = dp[i].first + x*x - 2*x*(f)(h[i]+1);
            lines[i]->slope = (f)(-2*(x-h[i]-1));
        }
        insert(tree, lines[i], 0, n);
    }
    /*cout << "dp: ";
    rep(i,0,n) {cout << dp[i].first - lambda*dp[i].second << "," << dp[i].second << " ";}
    cout << endl;*/
    return dp[n-1];
}

void build(node*v, ll l, ll r) { // [l,r)
    v->best = &inf;
    if (l+1==r) {
        v->lc = nullptr;
        v->rc = nullptr;
    } else {
        v->lc = new node;
        v->rc = new node;
        ll m = (l+r)/2;
        build(v->lc, l, m);
        build(v->rc, m, r);
    }
}

void insert(node*v, line*seg, ll l, ll r) {
    ll m = (l+r)/2;
    if (l+1==r) {
        if ((*v->best)(p[m].first) > (*seg)(p[m].first)) {swap(v->best,seg);}
        return;
    }
    // make seg the worse one (ie the larger one)
    if ((*v->best)(p[m].first) > (*seg)(p[m].first)) {swap(v->best,seg);}
    // no early returns bc whatever
    if ((*v->best).slope > (*seg).slope) {
        // The better (smaller) one has larger slope, which means the worse (larger) will undercut it later. Hence rc
        insert(v->rc, seg, m, r);
    } else {
        // The better (smaller) one has smaller slopw, which means the worse (larger) will undercut it before. Hence lc
        insert(v->lc, seg, l, m);
    }
}

pfl query(node*v, ll x, ll l, ll r) {
    ll m = (l+r)/2;
    if (l+1 == r) {return (*v->best)(p[x].first);}
    if (x < m) {
        return min((*v->best)(p[x].first), query(v->lc, x, l, m));
    } else {
        return min((*v->best)(p[x].first), query(v->rc, x, m, r));
    }
}

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