제출 #721967

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
721967		He_Huanglu	휴가 (IOI14_holiday)	C++17	0 / 100	95 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;
//        cout << l << " " << r << " " << sum(x) << " ^^\n";
        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);
//    cout << l << " " << r << " " << sum(x) << " ^^\n";
}

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;
//            cout << i << " " << mid << " " << cost << " ^^\n";
        }
//        cout << i << " " << j << " " << min(j - st, st - i) + j - i + k << "\n";
        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;
    for(int i = 1; i <= n; i++) {
        t[i] = new node(*t[i - 1]);
        upd(t[i], 0, maxn, a[i - 1]);
    }
//    long long ret = f(3);
    int l = 1, r = d, m;
    while (r - l > 4) {
        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++)
//        cout << i << " " << f(i) << "\n",
        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);
//}

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

holiday.cpp: In function 'void upd(node*, int, int, int)':
holiday.cpp:34:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     int mid = l + r >> 1;
      |               ~~^~~
holiday.cpp: In function 'long long int get(node*, node*, int, int, int)':
holiday.cpp:54:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |     int mid = l + r >> 1;
      |               ~~^~~
holiday.cpp: In function 'long long int f(int)':
holiday.cpp:74:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |             mid = l + r >> 1;
      |                   ~~^~~
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:96:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |         m = l + r >> 1;
      |             ~~^~~

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