Submission #622758

#	Time	Username	Problem	Language	Result	Execution time	Memory
622758		Lucpp	Aliens (IOI16_aliens)	C++17	4 / 100	2 ms	256 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e12+1;
const ll CINF = 1e6+1;

struct Lin{
    ll a, b; // a*x+b
    int cnt = 0;
    ll l, r;
    Lin(ll a_, ll b_, int cnt_ = 0, ll l_ = -CINF, ll r_ = CINF): a(a_), b(b_), cnt(cnt_), l(l_), r(r_) {}
    ll eval(ll x) {return a*x+b;}
};
ll sect(Lin f1, Lin f2){
    return (f2.b-f1.b) / (f1.a-f2.a);
}
deque<Lin> q;
void add(Lin f){
    while(!q.empty() && q.back().eval(q.back().l) >= f.eval(q.back().l)) q.pop_back();
    if(!q.empty()){
        q.back().r = sect(q.back(), f);
        f.l = q.back().r+1;
    }
    q.push_back(f);
}
ll qry(ll x){
    while(x > q.front().r) q.pop_front();
    return q.front().eval(x);
}
int cqry(ll x){
    while(x > q.front().r) q.pop_front();
    return q.front().cnt;
}

ll sq(ll x){return x*x;}

int n;
vector<pair<ll, ll>> a;
pair<ll, int> calc(ll lambda){
    q.clear();
    add(Lin(-2*a[0].first, sq(a[0].first)-2*a[0].first));
    ll dp = -1;
    int cnt = -1;
    for(int i = 0; i < n; i++){
        dp = sq(a[i].second+1) + qry(a[i].second) + lambda;
        cnt = cqry(a[i].second)+1;
        if(i < n-1){
            ll b = sq(a[i+1].first)-2*a[i+1].first - sq(max(0ll,a[i].second-a[i+1].first+1)) + dp;
            add(Lin(-2*a[i+1].first, b, cnt));
        }
    }
    return {dp, cnt};
}

ll take_photos(int N, int m, int k, vector<int> r, vector<int> c){
    n = N;
    m--; // suppress warning
    a.clear();
    vector<pair<int, int>> v;
    for(int i = 0; i < n; i++){
        v.emplace_back(min(r[i], c[i]), -max(r[i], c[i]));
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < n; i++){
        if(a.empty() || a.back().second < -v[i].second) a.emplace_back(v[i].first, -v[i].second);
    }
    n = (int)a.size();
    ll lo = 0, hi = INF;
    for(ll mid=(lo+hi)/2; lo<hi; mid=(lo+hi)/2){
        auto [dp, cnt] = calc(mid);
        if(cnt > k) lo = mid+1;
        else hi = mid;
    }
    auto [dp, cnt] = calc(lo);
    if(cnt > k) tie(dp, cnt) = calc(--lo);
    ll ans = dp - k*lo;
    return ans;
}

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