제출 #731159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
731159		becaido	Holiday (IOI14_holiday)	C++17	30 / 100	50 ms	3908 KiB

holiday

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

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

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1e5 + 5;

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

struct BIT {
    int tot, cnt[SIZE];
    ll all, sum[SIZE];
    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);
    while (rp < ql) add(++rp);
    while (rp > qr) del(rp--);

    ll mx = -1;
    int best;
    if (rp == ql) {
        FOR (i, ql, qr) {
            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 (i, 0, n - 1) a[i] = _a[i];

    iota(id, id + n, 0);
    sort(id, id + n, [](int lhs, int rhs) {
        return a[lhs] > a[rhs];
    });
    FOR (i, 0, n - 1) 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;
}

#ifdef WAIMAI
int main() {
    int n, start, d;
    int attraction[100000];
    int i, n_s;

    int x;
    cin >> x;

    ifstream in("sample-" + to_string(x) + ".in");
    ifstream in2("sample-" + to_string(x) + ".out");

    in >> n >> start >> d;
    FOR (i, 0, n - 1) in >> attraction[i];

    ll val = findMaxAttraction(n, start, d,  attraction), ans;
    in2 >> ans;

    cout << "ans = " << ans << ", val = " << val << '\n';
}
#endif

컴파일 시 표준 에러 (stderr) 메시지

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

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