Submission #1065964

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065964		PanosPask	Holiday (IOI14_holiday)	C++14	100 / 100	1764 ms	10312 KiB

holiday

#include <bits/stdc++.h>
#include "holiday.h"

using namespace std;

typedef long long ll;

const ll INF = 2e18;

struct SegTree {
    struct Node {
        ll sum = 0;
        int cnt = 0;
    };

    Node merge(Node a, Node b) {
        return {a.sum + b.sum, a.cnt + b.cnt};
    }

    int size;
    vector<Node> tree;

    void init(int N) {
        size = 1;

        while (size < N) {
            size *= 2;
        }

        tree.assign(2 * size, {0, 0});
    }

    void add(int i, Node v, int x, int lx, int rx) {
        if (lx == rx - 1) {
            tree[x] = merge(tree[x], v);
            return;
        }

        int mid = (lx + rx) / 2;
        if (i < mid) {
            add(i, v, 2 * x + 1, lx, mid);
        }
        else {
            add(i, v, 2 * x + 2, mid, rx);
        }

        tree[x] = merge(tree[2 * x + 1], tree[2 * x + 2]);
    }
    void add(int i, int x, int c) {
        add(i, {x, c}, 0, 0, size);
    }

    ll getsum(int k, int x, int lx, int rx) {
        if (k >= tree[x].cnt) {
            return tree[x].sum;
        }
        else if (tree[x].cnt == 0) {
            return 0;
        }
        else if (lx == rx - 1) {
            // Take **some** of these values
            ll v = tree[x].sum / tree[x].cnt;

            return v * k; 
        }

        ll res = 0;
        int mid = (lx + rx) / 2;
        res = getsum(k, 2 * x + 1, lx, mid);
        if (tree[2 * x + 1].cnt < k) {
            res += getsum(k - tree[2 * x + 1].cnt, 2 * x + 2, mid, rx);
        }

        return res;
    }
    ll getsum(int k) {
        return getsum(k, 0, 0, size);
    }
};

int N, D;
SegTree st;
vector<int> values;
vector<int> a;

int pos(int v)
{
    return values.size() - 1 - (lower_bound(values.begin(), values.end(), v) - values.begin());
}

void calculate(int s, int l, int r, int optl, int optr, int mod, vector<ll>& ans)
{
    if (optl >= N) {
        return;
    }

    int mid = (l + r) / 2;
    ll maxv = 0;
    int maxp = optl;
    
    for (int i = optl; i <= optr; i++) {
        st.add(pos(a[i]), a[i], 1);

        int rem = max(mid - (i - s) * mod, 0);
        ll cur = st.getsum(rem);

        if (cur > maxv) {
            maxv = cur;
            maxp = i;
        }
    }

    ans[mid] = maxv;

    for (int i = optl; i <= optr; i++) {
        st.add(pos(a[i]), -a[i], -1);
    }

    if (mid == l) {
        return;
    }

    calculate(s, l, mid, optl, maxp, mod, ans);

    for (int i = optl; i < maxp; i++) {
        st.add(pos(a[i]), a[i], 1);
    }
    calculate(s, mid, r, maxp, optr, mod, ans);
    for (int i = optl; i < maxp; i++) {
        st.add(pos(a[i]), -a[i], -1);
    }
}

long long int findMaxAttraction(int n, int start, int d, int attraction[])
{
    N = n;
    D = d;

    if (start == 0) {
        priority_queue<int, vector<int>, greater<int>> q;
 
        ll ans = 0;
        ll sum = 0;
 
        for (int i = 0; i < N && i <= d; i++) {
            q.push(attraction[i]);
            sum += attraction[i];
 
            int rem = d - i;
 
            while (q.size() > rem) {
                sum -= q.top();
                q.pop();
            }
 
            ans = max(ans, sum);
        }
 
        return ans;
    }

    values.resize(N);
    a.resize(N);

    for (int i = 0; i < N; i++) {
        values[i] = attraction[i];
        a[i] = attraction[i];
    }
    sort(values.begin(), values.end());
    values.resize(unique(values.begin(), values.end()) - values.begin());

    st.init(values.size());

    vector<ll> aft1(D + 1), aft2(D + 1);
    calculate(start, 0, D + 1, start + 1, N - 1, 1, aft1);
    calculate(start, 0, D + 1, start + 1, N - 1, 2, aft2);

    reverse(a.begin(), a.end());
    start = N - start - 1;
    vector<ll> bef1(D + 1), bef2(D + 1);
    calculate(start, 0, D + 1, start + 1, N - 1, 1, bef1);
    calculate(start, 0, D + 1, start + 1, N - 1, 2, bef2);

    ll ans = 0;
    for (int p1 = 0; p1 <= D; p1++) {
        int p2 = D - p1;

        ans = max(ans, aft1[p1] + bef2[p2]);
        ans = max(ans, bef1[p1] + aft2[p2]);

        if (p1) {
            ans = max(ans, aft1[p1 - 1] + a[start] + bef2[p2]);
            ans = max(ans, bef1[p1 - 1] + a[start] + aft2[p2]);
        }
        if (p2) {
            ans = max(ans, aft1[p1] + a[start] + bef2[p2 - 1]);
            ans = max(ans, bef1[p1] + a[start] + aft2[p2 - 1]);
        }
    }

    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:151:29: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  151 |             while (q.size() > rem) {
      |                    ~~~~~~~~~^~~~~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53