Submission #399536

#	Time	Username	Problem	Language	Result	Execution time	Memory
399536		Deemo	Aliens (IOI16_aliens)	C++14	100 / 100	279 ms	8800 KiB

aliens

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define F first
#define S second

const int MAXN = 1e6 + 10;

pii p[MAXN];
ll d[MAXN], intersect[MAXN], slope[MAXN];
ll better[MAXN];
int cnt[MAXN];
vector<pii> vec;

int sec[MAXN], sz;
ll eval(int id, ll x) {
    return intersect[id] + slope[id] * x;
}

ll get_time(int a, int b) {
    return (intersect[b] - intersect[a]) / (slope[a] - slope[b]) + 1;
}

void add_cand(int id) {
    intersect[id] = d[id] + 1ll*vec[id].F*vec[id].F;
    if (id && vec[id-1].S > vec[id].F)
        intersect[id] -= 1ll*(vec[id-1].S - vec[id].F) * (vec[id-1].S - vec[id].F);
    slope[id] = -2ll*vec[id].F;
    while (sz > 1 && get_time(sec[sz-1], id) <= get_time(sec[sz-2], sec[sz-1])) sz--;
    better[sz] = sz==0? -1ll: get_time(sec[sz-1], id);
    sec[sz++] = id;
}

pair<ll, int> get(ll mid) {
    int n = vec.size();
    d[0] = cnt[0] = 0;
    sz = 0;
    for (int i = 0; i < n; i++) {
        add_cand(i);
        int pos = upper_bound(better, better + sz, vec[i].S) - better - 1;
        d[i+1] = 1ll*vec[i].S*vec[i].S + eval(sec[pos], vec[i].S) + mid;
        cnt[i+1] = 1 + cnt[sec[pos]];
    }
    //cout << d[n] << "  " << cnt[n] << "   " << mid << endl;
    return {d[n], cnt[n]};
}

ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    for (int i = 0; i < n; i++) {
        p[i] = {r[i], c[i]};
        if (p[i].F > p[i].S)
            swap(p[i].F, p[i].S);
        p[i].S++;
    }
    sort(p, p + n, [](pii a, pii b) {
            if (a.F ^ b.F)
                return a.F < b.F;
            return a.S > b.S;
            });
    vec.clear();
    for (int i = 0; i < n; i++)
        if (vec.empty() || vec.back().S < p[i].S)
            vec.push_back(p[i]);
    //for (auto x: vec)
    //    cout << x.F << "     " << x.S << endl;
    n = vec.size();
    k = min(n, k);
    ll lo = -1, hi = 1ll*m*m;
    while (hi-lo>1){
        ll mid = hi+lo>>1;
        if (get(mid).S > k)
            lo = mid;
        else
            hi = mid;
    }
    auto x = get(hi);
    return x.F - 1ll*k * hi;
}
/*
int main() {
    //cout << take_photos(5, 7, 2, {0, 4, 4, 4, 4}, {3, 4, 6, 5, 6}) << "\n";
    //cout << take_photos(2, 6, 2, {1, 4}, {4, 1}) << "\n";
    cout << take_photos(2, 2, 1, {0, 1}, {0, 1}) << "\n";
    return 0;
}*/

Compilation message (stderr)

aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:74:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |         ll mid = hi+lo>>1;
      |                  ~~^~~

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