Submission #856582

#	Time	Username	Problem	Language	Result	Execution time	Memory
856582		fanwen	Holiday (IOI14_holiday)	C++17	100 / 100	161 ms	44364 KiB

holiday

#include <bits/stdc++.h>

#include "holiday.h"

using namespace std;

const int MAXN = 1e5 + 5;

int n, d, start, a[MAXN], root[MAXN];

long long ans = 0;
vector <int> cmp;

struct node_t {
    int le, ri, cnt = 0;
    long long sum = 0;
} it[18 * MAXN];

int Time;

void update(int pre, int nxt, int l, int r, int u, int val) {

    if(l > u || r < u || l > r) return;
    if(l == r) {
        it[nxt].sum = it[pre].sum + 1LL * val * cmp[l - 1];
        it[nxt].cnt = it[pre].cnt + val;
        return;
    }

    int mid = l + r >> 1;

    if(u <= mid) {
        it[nxt].ri = it[pre].ri;
        it[nxt].le = ++Time;
        update(it[pre].le, it[nxt].le, l, mid, u, val);
    } else {
        it[nxt].le = it[pre].le;
        it[nxt].ri = ++Time;
        update(it[pre].ri, it[nxt].ri, mid + 1, r, u, val);
    }

    it[nxt].cnt = it[it[nxt].le].cnt + it[it[nxt].ri].cnt;
    it[nxt].sum = it[it[nxt].le].sum + it[it[nxt].ri].sum;
}

long long getMax(int pre, int nxt, int l, int r, int cnt) {
    if(cnt <= 0) return 0;
    if(l == r) return 1LL * cnt * cmp[l - 1];

    int mid = l + r >> 1;

    int tmp = it[it[nxt].ri].cnt - it[it[pre].ri].cnt; 
    if(cnt <= tmp) return getMax(it[pre].ri, it[nxt].ri, mid + 1, r, cnt);
    long long ans = it[it[nxt].ri].sum - it[it[pre].ri].sum;
    ans += getMax(it[pre].le, it[nxt].le, l, mid, cnt - tmp);
    return ans;
}

void divide_and_conquer(int l, int r, int u, int v) {
    if(l > r) return;
    int mid = l + r >> 1;
    long long cost = -1;
    int p = u;
    for (int i = u; i <= v; ++i) {
        int L = start - mid, R = i - start, cnt = d - L - R - min(L, R);
        cnt = min(cnt, i - mid + 1);
        if(cnt < 0) continue;
        long long tmp = getMax(root[mid - 1], root[i], 1, n, cnt);
        if(cost < tmp) {
            cost = tmp;
            p = i;
        }
    }
    ans = max(ans, cost);
    divide_and_conquer(l, mid - 1, u, p);
    divide_and_conquer(mid + 1, r, p, v);
}

long long findMaxAttraction(int _n, int _start, int _d, int A[]) {
    ans = Time = 0;
    n = _n, d = _d, start = _start + 1;
    for (int i = 1; i <= n; ++i) a[i] = A[i - 1];
    cmp = vector <int> (a + 1, a + n + 1);
    sort(cmp.begin(), cmp.end()); cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
    for (int i = 1; i <= n; ++i) {
        a[i] = lower_bound(cmp.begin(), cmp.end(), a[i]) - cmp.begin() + 1;
    }
    // for (int i = 1; i <= n; ++i) cout << a[i] << " \n"[i == n];

    for (int i = 1; i <= n; ++i) {
        root[i] = ++Time;
        update(root[i - 1], root[i], 1, n, a[i], 1);
    }

    divide_and_conquer(1, start, start, n);
    return ans;
}
 
#ifdef LOCAL
 
#include<cstdio>
 
int main() {
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
    int n, start, d;
    int attraction[100000];
    int i, n_s;
    n_s = scanf("%d %d %d", &n, &start, &d);
    for (i = 0 ; i < n; ++i) {
        n_s = scanf("%d", &attraction[i]);
    }
    printf("%lld\n", findMaxAttraction(n, start, d,  attraction));
    return 0;
}
 
#endif // LOCAL
 
// Dream it. Wish it. Do it.

Compilation message (stderr)

holiday.cpp: In function 'void update(int, int, int, int, int, int)':
holiday.cpp:30:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |     int mid = l + r >> 1;
      |               ~~^~~
holiday.cpp: In function 'long long int getMax(int, int, int, int, int)':
holiday.cpp:50:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     int mid = l + r >> 1;
      |               ~~^~~
holiday.cpp: In function 'void divide_and_conquer(int, int, int, int)':
holiday.cpp:61:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |     int mid = l + r >> 1;
      |               ~~^~~

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