Submission #1216729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216729		nhphuc	Holiday (IOI14_holiday)	C++20	Compilation error	0 ms	0 KiB

holiday

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

const int N = 100100;

int n, st, d, piv, pos[N];
pair<int, int> a[N];
pair<int, long long> dpl[N], dpr[N], t[N * 4];

void upd (int id, int l, int r, int k, bool f){
    if (l == r){
        if (f){
            t[id] = {1, 1ll * a[k].first};
        } else {
            t[id] = {0, 0ll};
        }
        return;
    }
    int m = l + r >> 1;
    if (k <= m){
        upd(id * 2, l, m, k, f);
    } else {
        upd(id * 2 + 1, m + 1, r, k, f);
    }
    t[id] = make_pair(t[id * 2].first + t[id * 2 + 1].first, t[id * 2].second + t[id * 2 + 1].second);
    return;
}

long long get (int k){
    long long ans = 0;
    int id = 1, l = 1, r = n;
    while (l <= r){
        if (l == r){
            if (k >= t[id].first){
                ans += t[id].second;
            }
            break;
        }
        int m = l + r >> 1;
        if (k >= t[id * 2].first){
            k -= t[id * 2].first;
            ans += t[id * 2].second;
            id = id * 2 + 1;
            l = m + 1;
        }  else {
            r = m;
            id *= 2;
        }
    }
    return ans;
}

void dncl (int l, int r, int u, int v){
    if (l > r){
        return;
    }
    while (piv < u){
        ++piv;
        upd(1, 1, n, pos[piv], true);
    }
    while (piv > u){
        upd(1, 1, n, pos[piv], false);
        --piv;
    }
    int m = l + r >> 1;
    dpl[m] = {piv, get(m - (piv - st))};
    while (piv < v){
        ++piv;
        upd(1, 1, n, pos[piv], true);
        long long f = get(m - (piv - st));
        if (f > dpl[m].second){
            dpl[m] = {piv, f};
        }
    }
    dncl(l, m - 1, u, dpl[m].first);
    dncl(m + 1, r, dpl[m].first, v);
}

void dncr (int l, int r, int u, int v){
    if (l > r){
        return;
    }
    while (piv < v){
        upd(1, 1, n, pos[piv], false);
        ++piv;
    }
    while (piv > v){
        --piv;
        upd(1, 1, n, pos[piv], true);
    }
    int m = l + r >> 1;
    dpr[m] = {piv, get(m - (st - piv))};
    while (piv > u){
        --piv;
        upd(1, 1, n, pos[piv], true);
        long long f = get(m - (st - piv));
        if (f > dpr[m].second){
            dpr[m] = {piv, f};
        }
    }
    dncr(m + 1, r, u, dpr[m].first);
    dncr(l, m - 1, dpr[m].first, v);
}

int32_t main (){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    if (fopen ("test.inp", "r")){
        freopen ("test.inp", "r", stdin);
        freopen ("test.out", "w", stdout);
    }
    cin >> n >> st >> d; ++st;
    for (int i = 1; i <= n; ++i){
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a + 1, a + n + 1, greater<pair<int, int>>());
    for (int i = 1; i <= n; ++i){
        pos[a[i].second] = i;
    }
    piv = st - 1;
    dncl(0, d, st, min(st + d, n));
    fill(t, t + N * 4, make_pair(0, 0ll));
    piv = st;
    dncr(0, d, max(1, st - d), st - 1);
    long long res = 0;
    for (int i = 0; i <= d; ++i){
        int r = dpl[i].first;
        int lef = d - ((r - st) + i);
        res = max(res, dpl[i].second + (lef >= 0 ? dpr[lef].second : 0ll));
    }
    cout << res << "\n";
}

Compilation message (stderr)

holiday.cpp: In function 'int32_t main()':
holiday.cpp:108:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen ("test.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
holiday.cpp:109:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen ("test.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccC67nBn.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccsrB2zQ.o:holiday.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccC67nBn.o: in function `main':
grader.cpp:(.text.startup+0xaf): undefined reference to `findMaxAttraction(int, int, int, int*)'
collect2: error: ld returned 1 exit status