제출 #426248

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
426248		79brue	Aliens (IOI16_aliens)	C++14	100 / 100	232 ms	10140 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"

using namespace std;

typedef long long ll;

int n, m, k;
ll x[500002], y[500002];

void makeArr(vector<int>&, vector<int>&);
pair<ll, int> calc(ll);

ll take_photos(int N, int M, int K, vector<int> r, vector<int> c){
    m = M, k = K;
    makeArr(r, c);
    k = min(n, k);

    assert(calc(0).second == n);
    assert(calc(1e12*2+1).second == 1);

    ll L = 0, R = 1e12, ans = 1e12;
    while(L <= R){
        ll M = (L+R)>>1;
        if(calc(M).second <= k) ans = M, R = M-1;
        else L = M+1;
    }

    auto p = calc(ans);
    if(p.second == k) return p.first - ans * (k-1);

    auto p1 = calc(ans);
    auto p2 = calc(ans-1);
    assert(p1.second <= k && p2.second > k);
    int x1 = p1.second, x2 = p2.second;
    ll y1 = p1.first, y2 = p2.first;
    ll d1 = y1 - (x1-1) * ans, d2 = y2 - (x2-1) * (ans-1);
    return d2 + (d1 - d2) / (x2 - x1) * (x2 - k);
}

void makeArr(vector<int> &r, vector<int> &c){
    vector<pair<int, int> > vec;
    int N = (int)r.size();
    for(int i=0; i<N; i++){
        if(r[i] > c[i]) swap(r[i], c[i]);
        vec.push_back(make_pair(r[i], c[i]));
    }
    sort(vec.begin(), vec.end(), [&](pair<int, int> &x, pair<int, int> &y){
        return x.second < y.second;
    });

    vector<pair<int, int> > stk;
    for(int i=0; i<N; i++){
        if(!stk.empty() && stk.back().second == vec[i].second && stk.back().first <= vec[i].first) continue;
        while(!stk.empty() && stk.back().first >= vec[i].first) stk.pop_back();
        stk.push_back(vec[i]);
    }

    n = (int)stk.size();
    for(int i=1; i<=n; i++) x[i] = stk[i-1].first, y[i] = stk[i-1].second;

    for(int i=1; i<n; i++){
        assert(x[i] < x[i+1]);
        assert(y[i] < y[i+1]);
    }
}

ll quot(ll a, ll b){
    if(a>=0) return a/b;
    return a/b - !!(a%b);
}

struct Line{
    ll a, b; ll start; int cnt;
    Line(ll a, ll b, int cnt): a(a), b(b), cnt(cnt){}
    Line(ll a, ll b, ll start, int cnt): a(a), b(b), start(start), cnt(cnt){}

    ll val(ll x){
        return a*x+b;
    }

    ll cross(const Line &r)const{
        ll A = r.a - a;
        ll B = r.b - b;
        assert(A >= 0);
        return quot(-B+A-1, A);
    }
};

ll DP[500002];
int cnt[500002];
vector<Line> vec;
int pnt = 0;

pair<ll, int> calc(ll lambda){
    for(int i=1; i<=n; i++){
        DP[i] = (y[i] - x[1] + 1) * (y[i] - x[1] + 1);
        cnt[i] = 1;
    }
    pnt = 0;
    vec.clear();
    vec.push_back(Line(2, 3e12, -1e18, 0));

    for(int i=1; i<=n; i++){
        while(pnt >= (int)vec.size() || vec[pnt].start > y[i]) --pnt;
        while(pnt+1 < (int)vec.size() && y[i] >= vec[pnt+1].start) ++pnt;

        ll val = vec[pnt].val(y[i]) + y[i]*y[i] + lambda;
        if(DP[i] > val){
            DP[i] = val;
            cnt[i] = vec[pnt].cnt + 1;
        }

        if(i==n) break;
        Line tmp = Line(-(x[i+1]-1) * 2, (x[i+1]-1) * y[i] * 2 - y[i] * y[i] + DP[i], cnt[i]);
        if(x[i+1] > y[i]) tmp = Line(-(x[i+1]-1) * 2, (x[i+1]-1)*(x[i+1]-1) + DP[i], cnt[i]);

        while((int)vec.size() >= 2 && vec.back().start > tmp.cross(vec[(int)vec.size()-1])){
            vec.pop_back();
            if((int)vec.size() == pnt) pnt--;
        }
        tmp.start = tmp.cross(vec.back());
        vec.push_back(tmp);
    }

    return make_pair(DP[n], cnt[n]);
}

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