Submission #730086

#	Time	Username	Problem	Language	Result	Execution time	Memory
730086		nguyentunglam	Aliens (IOI16_aliens)	C++17	100 / 100	208 ms	9348 KiB

aliens

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 1e5 + 10;
pair<int, int> a[N];
long long l[N], r[N], f[N], g[N];
struct line {
    long long m, c;
    int idx;
    long long eval(long long x) { return m * x + c; }
    long long cut(line l) {
        return (c - l.c) / (l.m - m);
    }
};
struct CHT {
    line s[N];
    int st = 1, ed = 0;

    void add(line cur) {
//        cout << st << " " << ed << endl;
        while (ed - st + 1 >= 2 && cur.cut(s[ed]) <= s[ed].cut(s[ed - 1])) --ed;
        s[++ed] = cur;
    }

    line get(long long x) {
        while (ed - st + 1 >= 2 && s[st].eval(x) > s[st + 1].eval(x)) st++;
        return s[st];
    }
};

long long take_photos(int n, int m, int k, std::vector<int> RR, std::vector<int> CC) {
    for(int i = 0; i < n; i++) {
        a[i] = make_pair(RR[i], CC[i]);
        if (a[i].fi > a[i].se) swap(a[i].fi, a[i].se);
    }
    sort(a, a + n, [] (const ii &A, const ii &B) {
         if (A.fi != B.fi) return A.fi < B.fi;
         return A.se > B.se;
         });
    int n2 = 0, mx = -1;
    for(int i = 0; i < n; i++) if (a[i].se > mx) {
        mx = a[i].se;
        ++n2;
        l[n2] = a[i].fi;
        r[n2] = a[i].se;
    }
    n = n2;
    r[0] = -1;
    long long L = 0, R = 1e18, res = 1e18;
    while (L <= R) {
        long long mid = L + R >> 1;
        CHT cht;
        for(int i = 1; i <= n; i++) {
            long long cost = (l[i] <= r[i - 1]) ? (r[i - 1] - l[i] + 1) * (r[i - 1] - l[i] + 1) : 0;
            line cur = {-2LL * l[i], f[i - 1] - cost + l[i] * l[i], i - 1};
            cht.add(cur);
            line opt = cht.get(r[i] + 1);
            g[i] = g[opt.idx] + 1;

            f[i] = opt.eval(r[i] + 1) + (r[i] + 1) * (r[i] + 1) + mid;
        }
        if (g[n] <= k) {
            res = f[n] - mid * k;
            R = mid - 1;
        }
        else L = mid + 1;
    }
    return res;
}


#ifdef ngu
int main() {
    if (fopen ("task.inp", "r")) {
        freopen ("task.inp", "r", stdin);
        freopen ("task.out", "w", stdout);
    }
    int n, m, k; cin >> n >> m >> k;
    vector<int> r(n), c(n);
    for(int i = 0; i < n; i++) cin >> r[i] >> c[i];

    cout << take_photos(n, m, k, r, c);
//    cout << take_photos(5, 7, 3, {0, 4, 4, 4, 4}, {3, 4, 6, 5, 6});
//    cout <<  take_photos(2, 6, 2, {1, 4}, {4, 1});
}
#endif // ngu

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:54:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         long long mid = L + R >> 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