oj.uz

Submission #676819

# Submission time Handle Problem Language Result Execution time Memory
676819 2023-01-01T09:06:42 Z bashkort Holiday (IOI14_holiday) C++17
100 / 100
 668 ms 51764 KB 
#include "holiday.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int N = 100007;
constexpr int N_ = N * 18;
constexpr ll inf = 1e15;

struct Info {
    ll sum = 0;
    int cnt = 0;
};

int node_cnt = 1;

int L[N_], R[N_];
Info t[N_];

int create(int x) {
    int nx = node_cnt++;
    L[nx] = L[x], R[nx] = R[x], t[nx] = t[x];
    return nx;
}

void clear() {
    node_cnt = 1;
}

int modify(int i, int val, int x, int lx, int rx) {
    int nx = create(x);
    ++t[nx].cnt, t[nx].sum += val;

    if (lx + 1 < rx) {
        int mid = (lx + rx) >> 1;

        if (i < mid) {
            L[nx] = modify(i, val, L[x], lx, mid);
        } else {
            R[nx] = modify(i, val, R[x], mid, rx);
        }
    }

    return nx;
}

ll kth_sum(int k, int x, int lx, int rx) {
    if (lx + 1 == rx) {
        return t[x].sum;
    }

    int mid = (lx + rx) >> 1;

    if (t[R[x]].cnt > k) {
        return kth_sum(k, R[x], mid, rx);
    } else {
        k -= t[R[x]].cnt;
        return t[R[x]].sum + (k == 0 ? 0 : kth_sum(k, L[x], lx, mid));
    }
}

vector<ll> work(int d, vector<int> a) {
    if (a.empty()) {
        return vector<ll>(d + 1);
    }
    clear();
    int n = a.size();
    vector<pair<int, int>> yy;
    for (int i = 0; i < n; ++i) {
        if (a[i]) {
            yy.emplace_back(a[i], i);
        }
    }
    sort(yy.begin(), yy.end());

    vector<int> root(n);
    auto getValue = [&](int i, int opt) -> ll {
        if (i >= opt) {
            return 0;
        }

        return kth_sum(opt - i, root[i], 0, yy.size());
    };

    vector<pair<int, int>> stk; //i, opt

    int last = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] == 0) {
            continue;
        }
        int p = lower_bound(yy.begin(), yy.end(), pair{a[i], i}) - yy.begin();

        root[i] = modify(p, a[i], last, 0, yy.size());
        last = root[i];

        while (!stk.empty()) {
            auto [j, opt] = stk.back();

            if (getValue(j, opt) < getValue(i, opt)) {
                stk.pop_back();
            } else {
                break;
            }
        }

        if (stk.empty()) {
            stk.emplace_back(i, 0);
        } else {
            auto [j, opt] = stk.back();

            int lo = opt, hi = d + 1;
            while (lo + 1 < hi) {
                int mid = (lo + hi) >> 1;

                if (getValue(j, mid) < getValue(i, mid)) {
                    hi = mid;
                } else {
                    lo = mid;
                }
            }

            if (hi <= d) {
                stk.emplace_back(i, hi);
            }
        }
    }

    vector<ll> ans(d + 1);
    for (int i = d; i > 0; --i) {
        if (stk.empty()) {
            break;
        }

        ans[i] = getValue(stk.back().first, i);

        if (stk.back().second == i) {
            stk.pop_back();
        }
    }

    return ans;
}

ll solve(int n, int start, int d, vector<int> a) {
    vector<int> left, right;
    for (int i = start - 1; i >= 0; --i) {
        left.push_back(a[i]);
    }
    for (int i = start; i < n; ++i) {
        right.push_back(a[i]);
    }

    vector<ll> ansL = work(d, left);
    vector<ll> ansR = work(d, right);

    ll ans = 0;
    for (int i = 0; i <= d; ++i) {
        ans = max(ans, ansR[i]);
        if (i != d) {
            ans = max(ans, ansR[i] + ansL[d - i - 1]);
        }
    }

    return ans;
}

ll findMaxAttraction(int n, int start, int d, int attraction[]) {
    ll ans = 0;
    for (int _ = 0; _ < 2; ++_) {
        vector<int> now;
        for (int i = 0; i < start; ++i) {
            now.push_back(attraction[i]);
            now.push_back(0);
        }
        int s = now.size();
        for (int i = start; i < n; ++i) {
            now.push_back(attraction[i]);
        }

        ans = max(ans, solve(now.size(), s, d, now));

        reverse(attraction, attraction + n);
        start = n - start - 1;
    }
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 700 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 704 KB Output is correct
7 Correct 1 ms 700 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 50300 KB Output is correct
2 Correct 17 ms 8304 KB Output is correct
3 Correct 362 ms 50296 KB Output is correct
4 Correct 22 ms 8264 KB Output is correct
5 Correct 626 ms 44056 KB Output is correct
6 Correct 219 ms 15316 KB Output is correct
7 Correct 360 ms 24300 KB Output is correct
8 Correct 372 ms 29288 KB Output is correct
9 Correct 161 ms 12776 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1876 KB Output is correct
2 Correct 7 ms 1880 KB Output is correct
3 Correct 7 ms 1876 KB Output is correct
4 Correct 10 ms 1456 KB Output is correct
5 Correct 8 ms 1436 KB Output is correct
6 Correct 2 ms 980 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 2 ms 852 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 51764 KB Output is correct
2 Correct 668 ms 51736 KB Output is correct
3 Correct 99 ms 14680 KB Output is correct
4 Correct 5 ms 1228 KB Output is correct
5 Correct 2 ms 828 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 562 ms 25368 KB Output is correct
9 Correct 531 ms 25440 KB Output is correct