Submission #555785

#	Time	Username	Problem	Language	Result	Execution time	Memory
555785		nots0fast	Aliens (IOI16_aliens)	C++17	100 / 100	1245 ms	55600 KiB

aliens

#include "aliens.h"
#include <fstream>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <assert.h>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define ff first
#define setp setprecision(12)<<fixed
#define ss second
#define fori(v) for(ll i=0; i<v; i++)
#define forj(v) for(ll j=0; j<v; j++)
#define fork(v) for(ll k=0; k<v; k++)
#define forl(v) for(ll l=0; l<v; l++)
#define fort(v) for(ll t=0; t<v; t++)
#define forz(v) for(ll z=0; z<v; z++)
#define forx(v) for(ll x=0; x<v; x++)
#define ll long long
#define lll __int128
#define ld long double
#define pb(a) push_back(a)
// #define cout out
// #define cin in
ll inf = pow(10, 18);
ll modulo = pow(10,9) + 7;
double eps = 1e-10;
ifstream in;
ofstream out;


struct line{
    ll k, b;
    ll cnt;
    line(){}
    line(ll k1, ll b1, ll cn){
        k = k1, b = b1, cnt = cn;
    }    
};

ll func(line& cur, ll x){
    return cur.k * x + cur.b;
}

// min number of transitions
bool better(line& a, line& b, ll x){
    ll vl1 = func(a, x);
    ll vl2 = func(b, x);
    
    return (vl1 < vl2 || ( (vl1 == vl2) && (a.cnt < b.cnt) ));
}


#define MAX 2'100'010

line seg[MAX];
// ql = -inf, qr = inf

// O(q * log^2(n)) for range updates

void add(ll hd, ll l, ll r, ll ql, ll qr, line cur){
    if(qr < l || r < ql){
        return;
    }
    ll mid = (l+r)/2;
    if(ql <= l && r <= qr){
        // O(log(n))
        bool md = better(cur, seg[hd], mid);
        bool lf = better(cur, seg[hd], l) ;
        if(md){
                swap(seg[hd], cur);
        }
        if(l == r){
                return;
        }
        if(md == lf){
                add(2*hd + 1, mid+1, r, ql, qr, cur);
        }
        else{
                add(2*hd, l, mid, ql, qr, cur);
        }
    }
    else{
        add(2*hd + 1, mid+1, r, ql, qr, cur);
        add(2*hd, l, mid, ql, qr, cur);
    }
}

// [l ... r]

void que(ll hd, ll l, ll r , ll x, line& best){
    if(better(seg[hd], best, x)){
        best = seg[hd];
    }
    
    if(l == r){
        return;
    }
    
    ll mid = (l+r)/2;
    if(x <= mid){
        que(hd*2, l, mid, x, best);
    }
    else{
        que(hd*2+1, mid+1, r, x, best);
    }
}


bool J(pair<ll, ll>& a, pair<ll ,ll>& b){
      if(a.ff != b.ff){
            return a.ff < b.ff;
      }
      return a.ss > b.ss;
}

void calc(vector<pair<ll, ll> >& arr, vector<ll>& dp, vector<ll>& tot, ll& lamda, ll m){
    fori(MAX){
        seg[i] = line(0, inf, 0);
    }
    ll n = arr.size();
    dp = vector<ll>(n, inf);
    tot = vector<ll>(n, inf);
    dp[0] =0, tot[0] = 0;
    for(ll i = 1; i<n; i++){
        ll li = arr[i].ff, ri = arr[i].ss;
        ll rp = arr[i-1].ss;
        ll k, b;
        b = li * li + dp[i-1] - lamda;
        if(rp > li){
            b -= (rp - li) * (rp - li);
        }
        k = -2*li;
        add(1, 0, m, 0, m, line(k, b, tot[i-1] + 1));
        line best(0, inf, 0);
        que(1, 0, m, ri, best);
        
        dp[i] = func(best, ri) + ri*ri;
        tot[i] = best.cnt;
    }
}


long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    m+=10;
    vector<pair<ll, ll> > arr;
    fori(n){
        if(r[i] > c[i]){
            swap(r[i], c[i]);
        }
        arr.pb(mp(r[i], c[i]));
    }
    
    sort(arr.begin(), arr.end(), J);
    {
        ll mxc = -inf;
        vector<pair<ll, ll> > good({mp(-inf, -inf)});
        fori(n){
                ll ri = arr[i].ff, ci = arr[i].ss;
                if(ci > mxc){
                    good.pb(mp(ri, ci));
                    mxc = ci;
                }
        }
        arr = good;
    }
    n = arr.size();
    
    for(auto& el : arr){
        ++el.ss;
    }
    
    ll lo = -2e12, hi = 0;
    
    while(lo < hi){
        ll mid = (lo + hi)/2;
        // has to be closer to high
        if(hi - mid > mid - lo){
            ++mid;
        }
        
        vector<ll> dp, tot;
        calc(arr, dp, tot, mid, m);
        if(tot[n-1] > k){
            hi = mid-1;
        }
        else{
            lo = mid;
        }
    }
    
    vector<ll> dp, tot;
    calc(arr, dp, tot, lo, m);
    
//   cout<<"lamda is "<<lo<<" dp came out "<<dp[n-1]<<endl;
    
    // it is definitely k / or maybe smaller than k ????
    
    if(k == n){
        assert(lo == 0);
    }
    
    return dp[n-1] + k * lo;
}

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