oj.uz

Submission #731196

# Submission time Handle Problem Language Result Execution time Memory
731196 2023-04-27T06:55:45 Z becaido Holiday (IOI14_holiday) C++17
100 / 100
 199 ms 3668 KB 
#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

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.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 596 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 692 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3156 KB Output is correct
2 Correct 35 ms 3216 KB Output is correct
3 Correct 34 ms 3196 KB Output is correct
4 Correct 36 ms 3208 KB Output is correct
5 Correct 43 ms 3100 KB Output is correct
6 Correct 10 ms 1364 KB Output is correct
7 Correct 21 ms 1988 KB Output is correct
8 Correct 25 ms 2216 KB Output is correct
9 Correct 10 ms 1140 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 712 KB Output is correct
4 Correct 4 ms 708 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 2 ms 696 KB Output is correct
8 Correct 2 ms 688 KB Output is correct
9 Correct 2 ms 696 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3668 KB Output is correct
2 Correct 36 ms 3576 KB Output is correct
3 Correct 63 ms 2132 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 2 ms 704 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 199 ms 3656 KB Output is correct
9 Correct 196 ms 3652 KB Output is correct