Submission #367449

#	Time	Username	Problem	Language	Result	Execution time	Memory
367449		KoD	Holiday (IOI14_holiday)	C++17	100 / 100	762 ms	6692 KiB

holiday

#include <iostream>
#include <numeric>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>

#ifndef LOCAL
#include "holiday.h"
#endif

using ll = long long;
template <class T>
using Vec = std::vector<T>;

struct range {
    struct itr {
        ll i;
        itr(const ll i): i(i) { }
        ll operator * () const { return i; }
        void operator ++ () { i += 1; }
        bool operator != (const itr &other) { return i != other.i; }
    };
    const itr first, last;
    range(const ll begin, const ll end): first(begin), last(end) { }
    itr begin() const { return first; }
    itr end() const { return last; }
};

template <class T>
struct Fenwick {
    Vec<T> data;
    Fenwick() = default;
    Fenwick(const int n): data(n + 1) { }
    void add(int i, const T &x) {
        i += 1;
        while (i < (int) data.size()) {
            data[i] += x;
            i += i & -i;
        }
    }
    T get(int i) const {
        T ret = 0;
        while (i > 0) {
            ret += data[i];
            i -= i & -i;
        }
        return ret;
    }
    T fold(const int l, const int r) const {
        return get(r) - get(l);
    }
};

ll solve(const int n, const int start, const int days, const Vec<int> &score) {
    Vec<std::pair<int, int>> cmp;
    cmp.reserve(n);
    for (const int i: range(0, n)) {
        cmp.emplace_back(score[i], i);
    }
    std::sort(cmp.begin(), cmp.end());
    Vec<int> idx(n);
    for (const int i: range(0, n)) {
        idx[i] = std::lower_bound(cmp.begin(), cmp.end(), std::make_pair(score[i], i)) - cmp.begin();
    }
    Fenwick<int> count;
    Fenwick<ll> sum;
    const auto add = [&](const int i) {
        count.add(idx[i], 1);
        sum.add(idx[i], score[i]);
    };
    const auto remove = [&](const int i) {
        count.add(idx[i], -1);
        sum.add(idx[i], -score[i]);
    };
    int last_l = n, last_r = n;
    const auto query = [&](const int l, const int r) -> ll {
        const int travel = (start - l) + (r - l - 1);
        if (travel >= days) {
            return 0;
        }
        if (l < last_l || r < last_r) {
            count = Fenwick<int>(n);
            sum = Fenwick<ll>(n);
            last_l = l;
            last_r = l;
        }
        while (last_r < r) {
            add(last_r);
            last_r += 1;
        }
        while (last_l < l) {
            remove(last_l);
            last_l += 1;
        }
        const auto take = days - travel;
        int ok = n, ng = -1;
        while (ok - ng > 1) {
            const auto md = (ok + ng) / 2;
            if (count.fold(md, n) <= take) {
                ok = md;
            }
            else {
                ng = md;
            }
        }
        return sum.fold(ok, n);
    };
    std::queue<std::tuple<int, int, int, int>> que;
    que.emplace(0, start, start, n - 1);
    ll ret = 0;
    while (!que.empty()) {
        const auto [l, r, d, u] = que.front();
        que.pop();
        const auto m = (l + r) / 2;
        int select = d;
        ll score = 0;
        for (const auto i: range(d, u + 1)) {
            const auto tmp = query(m, i + 1);
            if (score < tmp) {
                select = i;
                score = tmp;
            }
        }
        ret = std::max(ret, score);
        if (l <= m - 1) {
            que.emplace(l, m - 1, d, select);
        }
        if (m + 1 <= r) {
            que.emplace(m + 1, r, select, u);
        }
    }
    return ret;
}

ll findMaxAttraction(int n, int start, int d, int attraction[]) {
    Vec<int> score(n);
    for (const int i: range(0, n)) {
        score[i] = attraction[i];
    }
    ll ret = solve(n, start, d, score);
    std::reverse(score.begin(), score.end());
    start = n - start - 1;
    ret = std::max(ret, solve(n, start, d, score));
    return ret;
}

#ifdef LOCAL
int main() {
    int n, s, d;
    std::cin >> n >> s >> d;
    int att[100] = {};
    for (const auto i: range(0, n)) {
        std::cin >> att[i];
    }
    std::cout << findMaxAttraction(n, s, d, att) << '\n';
    return 0;   
}
#endif

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