Submission #586014

#	Time	Username	Problem	Language	Result	Execution time	Memory
586014		MadokaMagicaFan	Holiday (IOI14_holiday)	C++14	100 / 100	2013 ms	15704 KiB

holiday

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;

#define sz(v)                       ((int)v.size())
#define pb                          push_back

#define pry                         cout << "YES\n"
#define prn                         cout << "NO\n"
#define endl                        '\n'

#define fst                         first
#define scn                         second

using pll = priority_queue<ll>;

int *a;
int s, n;

const int N = 1e5;
const int D = 2 * N + (N>>1);

int sind[N+2];
int sval[N+2];

int trk[4*N];
ll tr[4*N];

ll r1[D+2];
ll r2[D+2];
ll l1[D+2];
ll l2[D+2];

void
clear()
{
    for (int i = 0; i < 4*N; ++i) { tr[i] = 0; trk[i] = 0; }
    return;
}

ll
query(int i, int l, int r, int k)
{
    int mid = (l+r)>>1;
    if (k < 1) return 0;
    if (l == k) return tr[i];

    if (k >= trk[i]) return tr[i];

    return query(i<<1,l,mid,k) + query(i<<1|1,mid+1,r,k-trk[i<<1]);
}

ll
query(int k)
{
    return query(1,0,n-1,k);
}

void
upd(int i, int l, int r, int t, int v1, int v2)
{
    int mid = (l+r)>>1;
    if (l == r) {
        if (t != l) return;
        tr[i] = v1;
        trk[i] = v2;
        return;
    }

    if (l > t || r < t) return;

    upd(i<<1,l,mid,t,v1,v2);
    upd(i<<1|1,mid+1,r,t,v1,v2);

    tr[i] = tr[i<<1] + tr[i<<1|1];
    trk[i] = trk[i<<1] + trk[i<<1|1];

    return;
}

void
upd(int x, int v1, int v2)
{
    x = sind[x];
    upd(1,0,n-1,x,v1,v2);
    return;
}

void
computer1(int l, int r, int optl, int optr)
{
    int mid = (l+r)>>1;
    ll nv, best = -inf;
    int opt = optl;
    if (l > r) return;


    for (int i = optl; i <= optr; ++i) {
        if (abs(i-s) > mid) break;
        upd(i,a[i],1);
        nv = query(mid-abs(i-s));
        if (nv > best) {
            best = nv;
            opt = i;
        }
    }

    r1[mid] = best;

    for (int i = optl; i <= optr; ++i) upd(i,0,0);
    computer1(l,mid-1,optl,opt);
    for (int i = optl; i <= opt; ++i) upd(i,a[i],1);
    computer1(mid+1,r,opt,optr);

    return;
}

void
computer2(int l, int r, int optl, int optr)
{
    int mid = (l+r)>>1;
    ll nv, best = -inf;
    int opt = optl;
    if (l > r) return;


    for (int i = optl; i <= optr; ++i) {
        if (2*abs(i-s) > mid) break;
        upd(i,a[i],1);
        nv = query(mid-2*abs(i-s));
        if (nv > best) {
            best = nv;
            opt = i;
        }
    }

    r2[mid] = best;

    for (int i = optl; i <= optr; ++i) upd(i,0,0);
    computer2(l,mid-1,optl,opt);
    for (int i = optl; i <= opt; ++i) upd(i,a[i],1);
    computer2(mid+1,r,opt,optr);

    return;
}

void
computel1(int l, int r, int optl, int optr)
{
    int mid = (l+r)>>1;
    ll nv, best = -inf;
    int opt = optl;
    if (l > r) return;


    for (int i = optl; i >= optr; --i) {
        if (abs(i-s) > mid) break;
        upd(i,a[i],1);
        nv = query(mid-abs(i-s));
        if (nv > best) {
            best = nv;
            opt = i;
        }
    }

    l1[mid] = best;

    for (int i = optl; i >= optr; --i) upd(i,0,0);
    computel1(l,mid-1,optl,opt);
    for (int i = optl; i >= opt; --i) upd(i,a[i],1);
    computel1(mid+1,r,opt,optr);

    return;
}

void
computel2(int l, int r, int optl, int optr)
{
    int mid = (l+r)>>1;
    ll nv, best = -inf;
    int opt = optl;
    if (l > r) return;


    for (int i = optl; i >= optr; --i) {
        if (2*abs(i-s) > mid) break;
        upd(i,a[i],1);
        nv = query(mid-2*abs(i-s));
        if (nv > best) {
            best = nv;
            opt = i;
        }
    }

    l2[mid] = best;

    for (int i = optl; i >= optr; --i) upd(i,0,0);
    computel2(l,mid-1,optl,opt);
    for (int i = optl; i >= opt; --i) upd(i,a[i],1);
    computel2(mid+1,r,opt,optr);

    return;
}


ll
findMaxAttraction(int _n, int _s, int d, int _a[])
{
    vector<pair<int,int>> _v;

    a = _a;
    s = _s;
    n = _n;

    for (int i = 0; i < n; ++i) _v.pb({_a[i],i});

    sort(_v.begin(), _v.end());
    reverse(_v.begin(), _v.end());

    for (int i = 0; i < n; ++i) {
        sind[_v[i].scn] = i;
        sval[i] = _v[i].fst;
    }

    clear();
    computer1(0,d,s,n-1);
    clear();
    computer2(0,d,s,n-1);
    if (s) {
        clear();
        computel1(0,d,s-1,0);
        clear();
        computel2(0,d,s-1,0);
    }


    ll ans = max(l1[d],r1[d]);
    for (int i = 0; i < d+1; ++i) {
        ans = max(ans, l1[i] + r2[d-i]);
        ans = max(ans, r1[i] + l2[d-i]);
    }

    return ans;
}

#ifdef ONPC
void
solve()
{
    int n, s, d;
    cin >> n >> s >> d;
    int _a[n];
    for (int i = 0; i < n; ++i)
        cin >> _a[i];
    cout << findMaxAttraction(n,s,d,_a) << endl;
}

int32_t
main(int argc, char **argv)
{
    if (argc >= 2) {
        freopen(argv[1], "r", stdin);
    } else
        ios_base::sync_with_stdio(0);cin.tie(0);
    int t = 1;
    /* cin >> t; */
    while(t--)
        solve();
}
#endif

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