제출 #696426

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
696426		vjudge1	Holiday (IOI14_holiday)	C++17	100 / 100	525 ms	45788 KiB

holiday

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define fir first
#define sec second
typedef vector <int> vi;
typedef vector <ll> vl;
template <typename __Tp> void read(__Tp &x) {
    int f = 0; x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = 1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    if (f) x = -x;
}
template <typename __Tp1, typename ...__Tp2> void read(__Tp1 &x, __Tp2 &...y) { read(x), read(y...); }
template <typename __Tp> void write(__Tp x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + 48);
}
void write(char ch) { putchar(ch); }
template <typename __Tp1, typename ...__Tp2> void write(__Tp1 x, __Tp2 ...y) { write(x), write(y...); }

#include <holiday.h>
const int maxn = 3e5 + 10;
ll n, st, d, a[maxn], f[maxn][2], g[maxn][2], b[maxn], m;
struct SegTree {
    #define mid ((l + r) >> 1)
    int rt[maxn], ls[maxn << 5], rs[maxn << 5], cnt[maxn << 5], tot;
    ll sum[maxn << 5];
    void clr() { tot = 0; }
    void push_up(int o) {
        cnt[o] = cnt[ls[o]] + cnt[rs[o]];
        sum[o] = sum[ls[o]] + sum[rs[o]];
    }
    void update(int &p, int q, int l, int r, int pos) {
        p = ++tot, ls[p] = ls[q], rs[p] = rs[q], cnt[p] = cnt[q], sum[p] = sum[q];
        if (l == r) return cnt[p]++, sum[p] += b[l], void();
        pos <= b[mid] ? update(ls[p], ls[q], l, mid, pos) : update(rs[p], rs[q], mid + 1, r, pos), push_up(p);
    }
    ll query(int p, int q, int l, int r, int k) {
        if (cnt[q] - cnt[p] <= k) return sum[q] - sum[p];
        if (l == r) return k * b[l];
        if (cnt[rs[q]] - cnt[rs[p]] >= k) return query(rs[p], rs[q], mid + 1, r, k);
        return sum[rs[q]] - sum[rs[p]] + query(ls[p], ls[q], l, mid, k - (cnt[rs[q]] - cnt[rs[p]]));
    }
    #undef mid
} tr;
void calc(int flg) {
    tr.clr();
    for (int i = 1; i <= n; ++i) tr.update(tr.rt[i], tr.rt[i - 1], 0, m, a[i]);
    auto qry = [&] (int l, int r, int k) {
        k = max(0, min(k, r - l + 1));
        return tr.query(tr.rt[l - 1], tr.rt[r], 0, m, k);
    };
    auto ask = [&] (int d, int r, int flg) {
        if (!flg) return qry(st + 1, r, d - (r - st));
        else return qry(st + 1, r, d - (r - st) * 2);
    };
    function <void(ll, ll, ll, ll, ll)> solve = [&] (ll l, ll r, ll L, ll R, ll fl) {
        if (l > r || L == R) {
            for (int i = l; i <= r; ++i)
                if (!fl) f[i][flg] = ask(i, L, fl);
                else g[i][flg] = ask(i, L, fl);
            return;
        }
        ll mid = (l + r) >> 1, &val = (fl ? g[mid][flg] : f[mid][flg]), p = -1; val = -1;
        for (int i = L; i <= R; ++i) {
            ll tmp = ask(mid, i, fl);
            if (tmp > val) val = tmp, p = i;
        }
        solve(l, mid - 1, L, p, fl), solve(mid + 1, r, p, R, fl);
    };
    solve(0, d, st, n, 0), solve(0, d, st, n, 1);
}
ll findMaxAttraction(int _n, int _st, int _d, int _a[]) {
    ++_st;
    for (int i = _n; i >= 1; --i) _a[i] = _a[i - 1];
    n = m = _n, st = _st, d = _d;
    for (int i = 1; i <= n; ++i) a[i] = b[i] = _a[i];
    sort(b + 1, b + m + 1), m = unique(b + 1, b + m + 1) - b - 1;
    calc(0), reverse(a + 1, a + n + 1), st = n - st + 1, calc(1);
    ll ans = 0;
    for (int i = 0; i <= d; ++i)
        for (int c : {0, 1}) {
            ans = max(ans, f[i][c] + g[d - i][!c]);
            if (i < d) ans = max(ans, f[i][c] + g[d - i - 1][!c] + _a[_st]);
        }
    return ans;
}

// int n, st, d, a[maxn];

// int main() {
//     read(n, st, d);
//     for (int i = 0; i < n; ++i) read(a[i]);
//     write(Holiday :: findMaxAttraction(n, st, d, a), '\n');
//     return 0;
// }

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