Submission #882040

#	Time	Username	Problem	Language	Result	Execution time	Memory
882040		Pannda	Holiday (IOI14_holiday)	C++14	100 / 100	168 ms	44524 KiB

holiday

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

const int RES = 40e6;

struct SegmentTree {
    struct Node {
        long long sum = 0;
        int cnt = 0;
        int ln = 0, rn = 0;
    };

    int n;
    vector<int> dom;
    vector<Node> nodes;

    SegmentTree(int n, vector<int> dom) : n(n), dom(dom), nodes(1) {
        nodes.reserve(RES);
    }

    void add(int i, int base, int &aug, int l, int r) {
        aug = nodes.size();
        nodes.push_back(nodes[base]);
        nodes[aug].cnt++;
        nodes[aug].sum += dom[i];
        if (l + 1 < r) {
            int m = (l + r) >> 1;
            Node goat = nodes[aug];
            if (i < m) add(i, nodes[base].ln, goat.ln, l, m);
            else add(i, nodes[base].rn, goat.rn, m, r);
            nodes[aug] = goat;
        }
    }

    long long sum(int k, int idxl, int idxr, int l, int r) {
        if (l + 1 == r) {
            return 1LL * k * dom[l];
        } else {
            int m = (l + r) >> 1;
            int right_cnt = nodes[nodes[idxr].rn].cnt - nodes[nodes[idxl].rn].cnt;
            if (k >= right_cnt) {
                return sum(k - right_cnt, nodes[idxl].ln, nodes[idxr].ln, l, m) + nodes[nodes[idxr].rn].sum - nodes[nodes[idxl].rn].sum;
            } else {
                return sum(k, nodes[idxl].rn, nodes[idxr].rn, m, r);
            }
        }
    }

    void add(int i, int base, int &aug) { add(i, base, aug, 0, n); }
    long long sum(int k, int idxl, int idxr) { return sum(k, idxl, idxr, 0, n); }
};

long long findMaxAttraction(int n, int s, int d, int attraction[]) {
    vector<int> a(n);
    for (int i = 0; i < n; i++) a[i] = attraction[i];

    vector<int> dom = a;
    sort(dom.begin(), dom.end());
    dom.resize(unique(dom.begin(), dom.end()) - dom.begin());
    int C = dom.size();
    for (int &x : a) x = lower_bound(dom.begin(), dom.end(), x) - dom.begin();

    SegmentTree st(C, dom);
    vector<int> root(n + 1);
    root[0] = 0;
    for (int i = 0; i < n; i++) {
        st.add(a[i], root[i], root[i + 1]);
    }

    long long ans = 0;
    function<void(int, int, int, int)> compute = [&](int l, int r, int optl, int optr) {
        if (l > r) return;
        int m = (l + r) >> 1;
        long long f = 0;
        int opt = optl;
        for (int i = optl; i <= optr; i++) {
            int distance_to_walk = min(s - i, m - 1 - s) + m - 1 - i;
            int playtime = min(m - i, max(0, d - distance_to_walk));
            long long get = st.sum(playtime, root[i], root[m]);
            if (get > f) {
                f = get;
                opt = i;
            }
        }
        ans = max(ans, f);
        compute(l, m - 1, optl, opt);
        compute(m + 1, r, opt, optr);
    };

    compute(s + 1, n, 0, s);

    return ans;
}

//int main() {
//    ios::sync_with_stdio(false);
//    cin.tie(nullptr);
//    freopen("inp.inp", "r", stdin);
//    freopen("out.out", "w", stdout);
//
//    int n, s, d;
//    cin >> n >> s >> d;
//    int a[n];
//    for (int i = 0; i < n; i++) {
//        cin >> a[i];
//    }
//
//    cout << findMaxAttraction(n, s, d, a) << '\n';
//}

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