Submission #283986

#	Time	Username	Problem	Language	Result	Execution time	Memory
283986		Atill83	Aliens (IOI16_aliens)	C++14	100 / 100	239 ms	9588 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
const int MAXN = 1e5 + 5;
vector<pll> vc, vc2;
deque<pair<pll, int>>hull;
deque<ll> kes;
ll g[MAXN];
ll kc[MAXN];

ll eval(pll ln, ll idx){
    return ln.ff*idx + ln.ss;
}

ll iter(pll a, pll b){
    ll df1 = b.ss - a.ss;
    ll df2 = a.ff - b.ff;
    ll idx = df1 / df2 + ((df1 % df2) != 0)*((df1 < 0) ^ (df2 < 0)) * (-1);
    return idx;
}

pll gt(ll idx){
    while(!kes.empty() && kes[0] < idx){
        kes.pop_front();
        hull.pop_front();
    }
    return {eval(hull[0].ff, idx), hull[0].ss}; 
}

void add(ll a, ll b, int idx){
    if(hull.empty()){
        hull.push_back({{a, b}, idx});
        return;
    }
    while(!kes.empty() && eval({a, b}, kes.back()) <= eval(hull.back().ff, kes.back())){
        kes.pop_back();
        hull.pop_back();
    }
    kes.push_back(iter({a, b}, hull.back().ff));
    hull.push_back({{a, b}, idx});
}



pll check(ll C){
    int n = vc.size();
    hull.clear();
    kes.clear();
    g[0] = 0;
    kc[0] = 0;
    add(-2*(vc[0].ff - 1), (vc[0].ff - 1)*(vc[0].ff - 1), 0);
    for(int i = 1; i <= n; i++){
        pll u = gt(vc[i - 1].ss);
        g[i] = vc[i - 1].ss*vc[i - 1].ss + C + u.ff;
        kc[i] = kc[u.ss] + 1;
        if(i != n)
            add(-2*(vc[i].ff - 1), (vc[i].ff - 1)*(vc[i].ff - 1) - (ll)pow(max(vc[i - 1].ss - vc[i].ff + 1, 0LL), 2) + g[i], i);
    }
    return {g[n], kc[n]};
}




long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    for(int i = 0; i < n; i++){
        if(r[i] > c[i]) swap(r[i], c[i]);
        vc2.push_back({r[i], c[i]});
    }

    sort(vc2.begin(), vc2.end(), [](pii a, pii b){
        if(a.ff == b.ff) return a.ss > b.ss;
        return a.ff < b.ff;
    });
    pii lst = {-1, -1};
    for(int i = 0; i < n; i++){
        if(vc2[i].ss > lst.ss){
            vc.push_back(vc2[i]);
            lst = vc2[i];
        }
    }
    


    ll l = 0, rr = 1LL*m*m;
    //k = min(k, vc.size());
    while(l <= rr){
        ll m = (l + rr) / 2;
        pll ans = check(m);
        //cerr<<m<<" "<<ans.ff<<" "<<ans.ss<<endl;
        if(ans.ss <= k){
            rr = m - 1;
        }else{
            l = m + 1;
        }
    }
    pll ans = check(l);

    assert(ans.ss <= k);
    return ans.ff - k*l;
}

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