Submission #727873

#	Time	Username	Problem	Language	Result	Execution time	Memory
727873		He_Huanglu	Holiday (IOI14_holiday)	C++17	24 / 100	77 ms	65536 KiB

holiday

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5, maxn = 1e9;
int n, st, d, a[N];
long long res;

struct node {
    int sum;
    long long val;
    node *left, *right;
    node () {
        sum = 0, val = 0;
        left = right = nullptr;
    }
};
node *t[N];

int sum(node *p) {
    return p ? p->sum : 0;
}
long long val(node *p) {
    return p ? p->val : 0;
}

void upd(node *x, int l, int r, int pos) {
    if(l == r) {
        x->sum += 1;
        x->val += pos;
        return ;
    }
    int mid = l + r >> 1;
    if(pos <= mid) {
        x->left = x->left ? new node(*x->left) : new node();
        upd(x->left, l, mid, pos);
    }
    else {
        x->right = x->right ? new node(*x->right) : new node();
        upd(x->right, mid + 1, r, pos);
    }
    x->sum = sum(x->left) + sum(x->right);
    x->val = val(x->left) + val(x->right);
}

long long get(node *xl, node *xr, int l, int r, int k) {
    if(l == r) return l * min(k, sum(xr) - sum(xl));
    int mid = l + r >> 1;
    int cnt = sum(xr->right) - sum(xl->right);
    if(cnt > k) {
        xl->right = xl->right ? new node(*xl->right) : new node();
        xr->right = xr->right ? new node(*xr->right) : new node();
        return get(xl->right, xr->right, mid + 1, r, k);
    }
    else {
        xl->left = xl->left ? new node(*xl->left) : new node();
        xr->left = xr->left ? new node(*xr->left) : new node();
        return val(xr->right) - val(xl->right) + get(xl->left, xr->left, l, mid, k - cnt);
    }
}

long long cost(int l, int r) {
    int k = d - (r - l + min(st - l, r - st));
    if(k <= 0) return 0;
    return get(t[l - 1], t[r], 0, maxn, min(k, r - l + 1));
}

void solve(int l, int r, int optl, int optr) {
    if(l > r) return ;
    int mid = l + r >> 1;
    pair <long long, int> best;
    for(int i = optl; i <= min(mid, optr); i++) {
        best = max(best, {cost(i, mid), i});
    }
    res = max(res, best.first);
    solve(l, mid - 1, optl, best.second);
    solve(mid + 1, r, best.second, optr);
}

long long findMaxAttraction(int N, int Start, int D, int a[]) {
    t[0] = new node();
    n = N, d = D, st = Start + 1;
    for(int i = 1; i <= n; i++) {
        t[i] = new node(*t[i - 1]);
        upd(t[i], 0, maxn, a[i - 1]);
    }
    solve(st, n, 1, st);
    return res;
}

//main () {
//    cin.tie(0)->sync_with_stdio(0);
//    if(fopen("task.inp", "r")) {
//        freopen("task.inp", "r", stdin);
//        freopen("wa.out", "w", stdout);
//    }
//    cin >> n >> st >> d;
//    for(int i = 0; i < n; i++) cin >> a[i];
//    cout << findMaxAttraction(n, st, d, a);
//}

Compilation message (stderr)

holiday.cpp: In function 'void upd(node*, int, int, int)':
holiday.cpp:32:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     int mid = l + r >> 1;
      |               ~~^~~
holiday.cpp: In function 'long long int get(node*, node*, int, int, int)':
holiday.cpp:47:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |     int mid = l + r >> 1;
      |               ~~^~~
holiday.cpp: In function 'void solve(int, int, int, int)':
holiday.cpp:69:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |     int mid = l + r >> 1;
      |               ~~^~~

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