Submission #810183

#	Time	Username	Problem	Language	Result	Execution time	Memory
810183		htphong0909	Holiday (IOI14_holiday)	C++17	47 / 100	182 ms	65536 KiB

holiday

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;

void File() {

#define file "test"
    freopen(file".in", "r", stdin);
    freopen(file".out", "w", stdout);
}

int n, d, start;
long long ans = -1e18;

struct sum_kth_smallest {

    struct Node {
        long long sum;
        int cnt;
        int lCh, rCh;//children, indexes into `tree`
    };

    int mn, mx;
    vector<int> roots;
    deque<Node> tree;

    explicit sum_kth_smallest(const vector<int>& arr) : mn(INT_MAX), mx(INT_MIN), roots(arr.size() + 1, 0) {
        tree.push_back({0, 0, 0}); //acts as null
        for (int val : arr) mn = min(mn, val), mx = max(mx, val);
        for (int i = 0; i < (int)arr.size(); i++)
            roots[i + 1] = update(roots[i], -mx, mx, arr[i]);
    }
    int update(int v, int tl, int tr, int idx) {
        if (tl == tr) {
            tree.push_back({tree[v].sum + tl, tree[v].cnt + 1, 0, 0});
            return tree.size() - 1;
        }
        int tm = tl + (tr - tl) / 2;
        int lCh = tree[v].lCh;
        int rCh = tree[v].rCh;
        if (idx <= tm)
            lCh = update(lCh, tl, tm, idx);
        else
            rCh = update(rCh, tm + 1, tr, idx);
        tree.push_back({tree[lCh].sum + tree[rCh].sum, tree[lCh].cnt + tree[rCh].cnt, lCh, rCh});
        return tree.size() - 1;
    }


    int query(int l, int r, int k) const {
        assert(1 <= k && k <= r - l + 1); //note this condition implies L <= R
        assert(0 <= l && r + 1 < (int)roots.size());
        return query(roots[l], roots[r + 1], -mx, mx, k);
    }
    int query(int vl, int vr, int tl, int tr, int k) const {
        if (tl == tr)
            return tl;
        int tm = tl + (tr - tl) / 2;
        int left_count = tree[tree[vr].lCh].cnt - tree[tree[vl].lCh].cnt;
        if (left_count >= k) return query(tree[vl].lCh, tree[vr].lCh, tl, tm, k);
        return query(tree[vl].rCh, tree[vr].rCh, tm + 1, tr, k - left_count);
    }


    long long query_sum(int l, int r, int k) const {
        assert(1 <= k && k <= r - l + 1); //note this condition implies L <= R
        assert(0 <= l && r + 1 < (int)roots.size());
        return query_sum(roots[l], roots[r + 1], -mx, mx, k);
    }
    long long  query_sum(int vl, int vr, int tl, int tr, int k) const {
        if (tl == tr)
            return 1LL * tl * k;
        int tm = tl + (tr - tl) / 2;
        int left_count = tree[tree[vr].lCh].cnt - tree[tree[vl].lCh].cnt;
        long long left_sum = tree[tree[vr].lCh].sum - tree[tree[vl].lCh].sum;
        if (left_count >= k) return query_sum(tree[vl].lCh, tree[vr].lCh, tl, tm, k);
        return left_sum + query_sum(tree[vl].rCh, tree[vr].rCh, tm + 1, tr, k - left_count);
    }
};

int calcDis(int l, int r)
{
    if (l > r) return 0;
    if (start <= l) return(l - start + (r - l));
    if (start >= r) return(start - r + (r - l));
    return (min(start - l, r - start) + (r - l));
}

long long pf[1000001];

long long getSum(int l, int r)
{
    return (pf[r] - pf[l - 1]);
}

long long cost(int l, int r, const sum_kth_smallest& st)
{
    int k = max(d - calcDis(l, r), 0);
    k = min(r - l + 1, k);
    int ran = (r - l + 1);
    if (k == r - l + 1) return getSum(l, r);
    return (getSum(l, r) - st.query_sum(l, r, ran - k));
}

void divide(int l, int r, int gL, int gR, const sum_kth_smallest& st)
{
    if (l > r) return;
    int mid = (l + r) / 2;
    long long bestCost = -1e18;
    int bestPos = gL;
    for (int i = gL; i <= min(mid, gR); i++)
    {
        if (cost(i, mid, st) > bestCost)
        {
            bestCost = cost(i, mid, st);
            bestPos = i;
        }
    }
    ans = max(ans, bestCost);
    divide(l, mid - 1, gL, bestPos, st);
    divide(mid + 1, r, bestPos, gR, st);
}

long long findMaxAttraction(int _n, int _start, int _d, int *attraction)
{
    n = _n;
    d = _d;
    start = _start + 1;
    vector <int> arr(n + 1);
    for (int i = 1; i <= n; i++)
    {
        arr[i] = attraction[i - 1];
        pf[i] = pf[i - 1] + arr[i];
    }
    sum_kth_smallest st(arr);
    divide(1, n, 1, n, st);
    return ans;
}

/*
int test[10000001];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    File();
    cin >> n >> start >> d;
    for (int i = 1; i <= n; i++) cin >> test[i];
    cout << findMaxAttraction(n, start, d, test);
    return 0;
}*/

Compilation message (stderr)

holiday.cpp: In function 'void File()':
holiday.cpp:9:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     freopen(file".in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
holiday.cpp:10:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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