Submission #786195

#	Time	Username	Problem	Language	Result	Execution time	Memory
786195		phoebe	Aliens (IOI16_aliens)	C++17	Compilation error	0 ms	0 KiB

aliens

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define PB push_back
#define ALL(x) x.begin(), x.end()
#define FOR(i, n) for (int i = 0; i < n; i++)
#define NYOOM ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
const int INF = 1e9 + 7;
const ll LLINF = 1ll<<60;

const int maxn = 5e4 + 10;
int n, m, k, min_row[maxn * 4], max_col[maxn * 4];
pii points[maxn];
vector<int> dp_before(maxn), dp_cur(maxn);

void update_row(int x, int v, int tl = 0, int tr = maxn, int i = 1){
    if (tl > x || tr < x) return;
    if (tl == tr){
        min_row[i] = v; return;
    }
    int tm = (tl + tr) / 2;
    update_row(x, v, tl, tm, i * 2); update_row(x, v, tm + 1, tr, i * 2 + 1);
    min_row[i] = min(min_row[i * 2], min_row[i * 2 + 1]);
}

void update_col(int x, int v, int tl = 0, int tr = maxn, int i = 1){
    if (tl > x || tr < x) return;
    if (tl == tr){
        max_col[i] = v; return;
    }
    int tm = (tl + tr) / 2;
    update_col(x, v, tl, tm, i * 2); update_col(x, v, tm + 1, tr, i * 2 + 1);
    max_col[i] = max(max_col[i * 2], max_col[i * 2 + 1]);
}

int range_row(int l, int r, int tl = 0, int tr = maxn, int i = 1){
    if (l > tr || tl > r) return LLINF;
    if (l <= tl && tr <= r) return min_row[i];
    int tm = (tl + tr) / 2;
    return min(range_row(l, r, tl, tm, i * 2), 
    range_row(l, r, tm + 1, tr, i * 2 + 1));
}

int range_col(int l, int r, int tl = 0, int tr = maxn, int i = 1){
    if (l > tr || tl > r) return -1;
    if (l <= tl && tr <= r) return max_col[i];
    int tm = (tl + tr) / 2;
    return max(range_col(l, r, tl, tm, i * 2), 
    range_col(l, r, tm + 1, tr, i * 2 + 1));
}

int cost(int l, int r){ // [l, r]
    int row = range_row(l, r), col = range_col(l, r);
    return (col - row + 1) * (col - row + 1);
}

void solve(int l, int r, int optl, int optr){
    if (l > r) return;
    int mid = (l + r) / 2;
    dp_cur[mid] = LLINF; int opt = -1;
    for (int k = optl; k <= min(mid, optr); k++){
        int v = cost(k, mid);
        if (k != 0) v += dp_before[k - 1];
        if (v < dp_cur[mid]) dp_cur[mid] = v, opt = k;
    }
    solve(l, mid - 1, optl, opt);
    solve(mid + 1, r, opt, optr);
}

signed main(){
    NYOOM;
    fill(min_row, min_row + maxn * 4, INF);
    fill(max_col, max_col + maxn * 4, -1);
    cin >> n >> m >> k;
    FOR(i, n){
        cin >> points[i].F >> points[i].S;
        if (points[i].S < points[i].F) swap(points[i].F, points[i].S);
    }
    sort(points, points + n);
    FOR(i, n){
        int r = points[i].F, c = points[i].S;
        update_row(i, r); update_col(i, c);
    }
    FOR(i, n) dp_before[i] = cost(0, i);
    for (int i = 2; i <= k; i++){
        solve(0, n - 1, 0, n - 1);
        dp_before = dp_cur;
    }
    cout << dp_before[n - 1];
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccUV2cSD.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccJwlbuD.o:aliens.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccUV2cSD.o: in function `main':
grader.cpp:(.text.startup+0xf0): undefined reference to `take_photos(int, int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status