Submission #1218251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218251		Hamed_Ghaffari	Holiday (IOI14_holiday)	C++20	100 / 100	944 ms	5064 KiB

holiday

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

using ll = long long;

#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)

const int MXN = 1e5+5;

int n, start, d, cnt[MXN<<2], ord[MXN], a[MXN], pos[MXN];
ll sum[MXN<<2];

void upd(int p, bool ac, int l=0, int r=n+1, int id=1) {
    if(r-l == 1) {
        cnt[id] = ac;
        sum[id] = ac ? a[ord[l]] : 0;
        return;
    }
    p<mid ? upd(p, ac, l, mid, lc) : upd(p, ac, mid, r, rc);
    cnt[id] = cnt[lc] + cnt[rc];
    sum[id] = sum[lc] + sum[rc];
}

int cnt_;
ll sum_;
void get_(int l=0, int r=n+1, int id=1) {
    if(r-l == 1) return;
    if(cnt[lc]<=cnt_) {
        sum_ += sum[lc];
        cnt_ -= cnt[lc];
        get_(mid, r, rc);
    }
    else get_(l, mid, lc);
}

inline ll get(int k) {
    cnt_ = k;
    sum_ = 0;
    get_();
    return sum_;
}

int L=1, R=0;

inline void adjust(int l, int r) {
    while(R<r) upd(pos[++R], 1);
    while(L>l) upd(pos[--L], 1);
    while(R>r) upd(pos[R--], 0);
    while(L<l) upd(pos[L++], 0);
}

ll ans;

void dnql(int l, int r, int opl, int opr) {
    if(l>r) return;
    ll cur = -1, tmp;
    int op = opl;
    for(int i=max(mid, opl); i<=opr && start+i-2*mid<=d; i++) {
        adjust(mid, i);
        tmp = get(d - (start+i-2*mid));
        if(tmp>cur) {
            cur = tmp;
            op = i;
        }
    }
    ans = max(ans, cur);
    dnql(l, mid-1, opl, op);
    dnql(mid+1, r, op, opr);
}

void dnqr(int l, int r, int opl, int opr) {
    if(l>r) return;
    ll cur = -1, tmp;
    int op = opl;
    for(int i=min(mid,opr); i>=opl && 2*mid-start-i<=d; i--) {
        adjust(i, mid);
        tmp = get(d - (2*mid-start-i));
        if(tmp>cur) {
            cur = tmp;
            op = i;
        }
    }
    ans = max(ans, cur);
    dnqr(l, mid-1, opl, op);
    dnqr(mid+1, r, op, opr);
}

ll findMaxAttraction(int n, int start, int d, int attraction[]) {
    ::n = n;
    ::start = start;
    ::d = d;
    for(int i=0; i<n; i++) a[i] = attraction[i], ord[i] = i;
    sort(ord, ord+n, [&](int i, int j) {
        return a[i] > a[j];
    });
    for(int i=0; i<n; i++) pos[ord[i]] = i;
    dnql(max(0, start-d), start, 0, n-1);
    dnqr(start, min(n-1, start+d), 0, n-1);
    return ans;
}

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