Submission #721974

#	Time	Username	Problem	Language	Result	Execution time	Memory
721974		He_Huanglu	Holiday (IOI14_holiday)	C++17	0 / 100	75 ms	65536 KiB

holiday

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

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

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 *sl, node *sr, int l, int r, int k) {
    int ret = 0;
    if(l == r) {
       ret = l * min(k, sum(sr->right) - sum(sl->right));
       return ret;
    }
    int mid = l + r >> 1;
    int num = sum(sr->right) - sum(sl->right);
    if(num > k) {
        sl->right = sl->right ? new node(*sl->right) : new node();
        sr->right = sr->right ? new node(*sr->right) : new node();
        ret = get(sl->right, sr->right, mid + 1, r, k);
        return ret;
    }
    sl->left = sl->left ? new node(*sl->left) : new node();
    sr->left = sr->left ? new node(*sr->left) : new node();
    ret = val(sr->right) - val(sl->right) + get(sl->left, sr->left, l, mid, k - num);
    return ret;
}

long long f(int k) {
    int rest = d - k, lim = max(1, st - rest);
    long long ret = 0;
    for(int i = st; i >= lim; i--) {
        int l = st, r = n, mid, j = 0;
        while (l <= r) {
            mid = l + r >> 1;
            int cost = min(mid - st, st - i) + mid - i + k;
            if(cost <= d) l = mid + 1, j = mid;
            else r = mid - 1;
        }
        if(j) ret = max(ret, get(t[i - 1], t[j], 0, maxn, k));
    }
    return ret;
}

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]);
    }
    int l = 1, r = d, m;
    while (r - l > 2) {
        m = l + r >> 1;
        if(f(m) < f(m + 1)) l = m;
        else r = m + 1;
    }
    long long ret = 0;
    for(int i = l; i <= r; i++) ret = max(ret, f(i));
    return ret;
}

//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:33:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |     int mid = l + r >> 1;
      |               ~~^~~
holiday.cpp: In function 'long long int get(node*, node*, int, int, int)':
holiday.cpp:52:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     int mid = l + r >> 1;
      |               ~~^~~
holiday.cpp: In function 'long long int f(int)':
holiday.cpp:72:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |             mid = l + r >> 1;
      |                   ~~^~~
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:91:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |         m = l + r >> 1;
      |             ~~^~~

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