Submission #731196

#	Time	Username	Problem	Language	Result	Execution time	Memory
731196		becaido	Holiday (IOI14_holiday)	C++17	100 / 100	199 ms	3668 KiB

holiday

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;

using ll = long long;

const int N = 1e5 + 5;

int n, s, d;
ll ans;
int a[N], id[N], p[N], lp, rp;

struct BIT {
    int tot, cnt[N];
    ll all, sum[N];
    void init() {
        tot = all = 0;
        fill(cnt + 1, cnt + n + 1, 0);
        fill(sum + 1, sum + n + 1, 0);
    }
    void upd(int pos, int x, int val) {
        tot += x;
        all += val;
        for (; pos <= n; pos += pos & -pos) {
            cnt[pos] += x;
            sum[pos] += val;
        }
    }
    ll que(int k) {
        if (k <= 0) return 0;
        if (k >= tot) return all;
        int pos = 0, cur = 0;
        ll re = 0;
        for (int i = __lg(n); i >= 0; i--) if (pos + (1 << i) <= n && cur + cnt[pos + (1 << i)] <= k) {
            cur += cnt[pos + (1 << i)];
            re += sum[pos += 1 << i];
        }
        return re;
    }
} bit;

inline void add(int i) {
    if (0 <= i && i < n) bit.upd(p[i], 1, a[i]);
}
inline void del(int i) {
    if (0 <= i && i < n) bit.upd(p[i], -1, -a[i]);
}

void divide(int l, int r, int ql, int qr) {
    if (l > r) return;
    int mid = (l + r) / 2;
    while (lp >= mid) add(lp--);
    while (lp < mid - 1) del(++lp);
    if (ql < rp && rp < qr) {
        if (rp - ql < qr - rp) while (rp > ql) del(rp--);
        else while (rp < qr) add(++rp);
    }
    while (rp < ql) add(++rp);
    while (rp > qr) del(rp--);

    ll mx = -1;
    int best;
    if (rp == ql) {
        for (int i = ql; i <= qr; i++) {
            ll val = bit.que(d - 2 * (s - mid) - (i - s));
            if (val > mx) {
                mx = val;
                best = i;
            }
            add(++rp);
        }
    } else {
        for (int i = qr; i >= ql; i--) {
            ll val = bit.que(d - 2 * (s - mid) - (i - s));
            if (val > mx) {
                mx = val;
                best = i;
            }
            del(rp--);
        }
    }
    ans = max(ans, mx);
    divide(l, mid - 1, ql, best);
    divide(mid + 1, r, best, qr);
}

ll findMaxAttraction(int _n, int _s, int _d, int _a[]) {
    ans = 0;
    n = _n, s = _s, d = _d;
    for (int i = 0; i < n; i++) a[i] = _a[i];
    iota(id, id + n, 0);
    sort(id, id + n, [](int lhs, int rhs) {
        return a[lhs] > a[rhs];
    });
    for (int i = 0; i < n; i++) p[id[i]] = i + 1;
    bit.init();
    lp = rp = s;
    divide(0, s, s, n - 1);
    s = n - s - 1;
    reverse(a, a + n);
    reverse(p, p + n);
    bit.init();
    lp = rp = s;
    divide(0, s, s, n - 1);
    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void divide(int, int, int, int)':
holiday.cpp:85:11: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |     divide(l, mid - 1, ql, best);
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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