Submission #397181

#	Time	Username	Problem	Language	Result	Execution time	Memory
397181		Deemo	Aliens (IOI16_aliens)	C++14	0 / 100	1 ms	332 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)) / (slope[a] - slope[b]);
}

void add_cand(int id) {
    intersect[id] = d[id] + 1ll*vec[id].F*vec[id].F;
    slope[id] = -2ll*vec[id].F;
    while (sz > 1 && get_time(sec[sz-2], 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 = lower_bound(better, better + sz, vec[i].S) - better;
        if (pos == sz || better[pos] > vec[i].S) pos--;
        d[i+1] = 1ll*vec[i].S*vec[i].S + eval(sec[pos], vec[i].S) + mid;
        cnt[i+1] = 1 + cnt[sec[pos]];

        if (i && vec[i-1].S > vec[i].F) {
            d[i] -= 1ll*(vec[i-1].S - vec[i].F) * (vec[i-1].S * vec[i].F);
            while (sz > 2 && get_time(sec[sz-3], sec[sz-1]) < get_time(sec[sz-3], sec[sz-2])) {
                sec[sz-2] = sec[sz-1];
                sz--;
            }
        }
    }
    //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]);
    n = vec.size();
    ll lo = -1, hi = 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);
    if (x.S != k) {
        auto y = get(lo);
        x.F -= x.S * hi;
        y.F -= y.S * lo;
        int dif = y.S - x.S;
        ll ans = x.F + (x.F - y.F) * dif / (k - x.S);
        return ans;
    }
    return x.F - x.S * hi;
}
/*
// TODO remove
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";
    return 0;
}*/

Compilation message (stderr)

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

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