Submission #446658

#	Time	Username	Problem	Language	Result	Execution time	Memory
446658		Kepha	Holiday (IOI14_holiday)	C++11	Compilation error	0 ms	0 KiB

holiday

// IOI 2014 Day 2 Problem 3 holiday
#include <bits/stdc++.h>
#define int long long
#define MX 100000
#define pii pair<int, int>
using namespace std;
using namespace chrono;

struct SegTree{
    const int VALUE = 0;
    int size, n;
    vector<int> sums, active; // sums is [0...2*size-1]

    void init(int n) {
        size = 1;
        while (size < n) size *= 2;
        sums.assign(2 * size, VALUE);
        active.assign(2 * size, 0);
    }

    int query(int node, int x) {
        if (active[node] <= x) return sums[node];
        // if (node >= size) return sums[node];

        if (active[node * 2 + 1] > x)
            return query(node * 2 + 1, x);
        else if (active[node * 2 + 1] == x)
            return sums[node * 2 + 1];
        else return query(node * 2, x - active[node * 2 + 1]) + sums[node * 2 + 1];
    }

    // assumes pos is 1 - based
    void update(int pos, int value, int act) {
        if (pos == 0) return;

        pos += size - 1;
        sums[pos] = value;
        // do we activate?
        active[pos] = act;
        for (pos /= 2; pos >= 1; pos /= 2) {
            sums[pos] = sums[pos * 2] + sums[pos * 2 + 1];
            active[pos] = active[pos * 2] + active[pos * 2 + 1];
        }
    }
};

int N, start, d, NL, NR;
// sorted arrays
vector<pii> Left, Right;
// occ[i] = index after sorting
vector<int> occLeft, occRight;
// active range, based on indices of a single range
int curL = 0, curR = 0;
// g[i] = [1, start) when d = i, f[i] = [start, N] when d = i
vector<pii> f, g;
SegTree seg;

int Arr[MX + 1];

// need to take care of 0
// A is either Left/Right, occ is either occLeft/occRight
void activate(int L, int R, vector<pii> A, vector<int> occ) {
    while (curL > L) curL--, seg.update(occ[curL], A[occ[curL]].first, 1);
    while (curR < R) curR++, seg.update(occ[curR], A[occ[curR]].first, 1);
    while (curL < L) seg.update(occ[curL], 0, 0), curL++;
    while (curR > R) seg.update(occ[curR], 0, 0), curR--;
}

// pos, cnt
pii search(int l, int r, int curd, vector<pii> A, vector<int> occ) {
    activate(0, l - 1, A, occ);

    pii ans = {-1, -1};

    for (int i = l; i <= r; i++) {
        if (curd - i + 1 <= 0) break;
        seg.update(occ[i], A[occ[i]].first, 1);
        ++curR;
        int val = seg.query(1, curd - i + 1); // start at 1, so (i - 1)
        if (val > ans.second)
            ans = {i, val};
    }

    return ans;
}

// l, r here means d. optl, optr means positions to search
void dfs(int l, int r, int optl, int optr, 
        vector<pii> A, vector<int> occ, vector<pii>& V) {
    if (l > r) return;

    int mid = (l + r) / 2;
    V[mid] = search(optl, optr, mid, A, occ);
    int opt = V[mid].first;

    dfs(l, mid - 1, optl, opt, A, occ, V);
    dfs(mid + 1, r, opt, optr, A, occ, V);
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N >> start >> d;
    start++;

    NL = start - 1, NR = N - start + 1;

    Left.resize(NL + 1);
    occLeft.resize(NL + 1, 0);
    Right.resize(NR + 1);
    occRight.resize(NR + 1, 0);
    f.resize(d + 1);
    g.resize(d + 1);

    for (int i = 1; i <= N; i++) {
        int x; cin >> x; Arr[i] = x;
        if (i < start) Left[i] = {x, i};
        else Right[i - start + 1] = {x, i - start + 1};
    }

    sort(Left.begin() + 1, Left.begin() + 1 + NL);
    sort(Right.begin() + 1, Right.begin() + 1 + NR);

    for (int i = 1; i <= NL; i++)
        occLeft[Left[i].second] = i;

    for (int i = 1; i <= NR; i++)
        occRight[Right[i].second] = i;

    // g(), RIGHT PART
    seg.init(NR + 1);
    f[0] = {1, 0};

    if (NR > 0)
        dfs(1, d, 1, NR, Right, occRight, f);

    // f(), LEFT PART
    seg.init(NL + 1);

    // originally we traverse occLeft from start - 1 to 1, 
    // now we reverse the list and traverse from 1 to start - 1 
    reverse(occLeft.begin() + 1, occLeft.begin() + 1 + NL);
    curL = curR = 0;
    g[0] = {1, 0};

    if (NL > 0)
        dfs(1, d, 1, NL, Left, occLeft, g);

    // FINAL ANSWER
    int ans = 0;

    // go to right, then left
    for (int d0 = 0; d0 <= d; d0++) {
        int cnt = f[d0].second;
        int cost = d - d0 - (f[d0].first - 1) - 1;

        ans = max(ans, cnt);
        if (cost < 0) continue;

        cnt += g[cost].second;
        ans = max(ans, cnt);
    }

    // go to left, then right
    for (int d0 = 1; d0 <= d; d0++) {
        int cnt = g[d0 - 1].second;
        int cost = d - d0 - (g[d0 - 1].first - 1) - 1;

        ans = max(ans, cnt);
        if (cost < 0) continue;

        cnt += f[cost].second;
        ans = max(ans, cnt);
    }

    cout << ans << "\n";
    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccJ6LgZq.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc4jHwDt.o:holiday.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccJ6LgZq.o: in function `main':
grader.cpp:(.text.startup+0xaf): undefined reference to `findMaxAttraction(int, int, int, int*)'
collect2: error: ld returned 1 exit status