Submission #392054

#	Time	Username	Problem	Language	Result	Execution time	Memory
392054		Aldas25	Holiday (IOI14_holiday)	C++14	100 / 100	2410 ms	15564 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<int> vi;

const int MAXN = 500100;

ll a[MAXN];
int n, start;

vector<pair<ll, int>> srt;
int to[MAXN];

ll tree[4*MAXN], cnt[4*MAXN];

void build (int id = 1, int le = 0, int ri = n-1) {
    if (le == ri) {
        tree[id] = 0;
        cnt[id] = 0;
        return;
    }
    int mid = (le+ri)/2;
    build (2*id, le, mid);
    build (2*id+1, mid+1, ri);
    tree[id] = tree[2*id] + tree[2*id+1];
    cnt[id] = cnt[2*id] + cnt[2*id+1];
}

void turn (bool on, int p, int id = 1, int le = 0, int ri = n-1) {
    if (le == ri) {
        if (on) {
            tree[id] = srt[le].f;
            cnt[id] = 1;
        } else {
            tree[id] = 0;
            cnt[id] = 0;
        }
        return;
    }
    int mid = (le+ri)/2;
    if (p <= mid)
        turn (on, p, 2*id, le, mid);
    else
        turn (on, p, 2*id+1, mid+1, ri);
    tree[id] = tree[2*id] + tree[2*id+1];
    cnt[id] = cnt[2*id] + cnt[2*id+1];
}

void turnOn (int p) {
    p = to[p];
    turn (1, p);
}

void turnOff (int p) {
    p = to[p];
    turn (0, p);
}

ll get (int x, int id = 1, int le = 0, int ri = n-1) {
    if (x <= 0) return 0;
    if (cnt[id] <= x) return tree[id];
    int mid = (le+ri)/2;
    return get(x, 2*id, le, mid) + get(x-cnt[2*id], 2*id+1, mid+1, ri);
}

ll f[MAXN], ansF[MAXN];
ll g[MAXN], ansG[MAXN];

void rec (int le, int ri, int fr, int to, int moved = 0) {
    int m = (le+ri)/2;
    ansF[m] = -1;
    FOR(i, fr, to) {
        int remD = m - moved - (i-fr);
        if (remD <= 0) break;
        turnOn(i);
        ll cur = get(remD);
        if (cur > ansF[m]) {
            ansF[m] = cur;
            f[m] = i;
        }
    }

    if (ansF[m] == -1) {
        ansF[m] = 0;
        f[m] = fr;
    }

    FOR(i, fr, to) turnOff(i);

    if (le <= m-1) rec(le, m-1, fr, f[m], moved);

    FOR(i, fr, f[m]-1) {
        moved++;
        turnOn(i);
    }
    if (m+1 <= ri) rec(m+1, ri, f[m], to, moved);
    FOR(i, fr, f[m]-1) {
        moved--;
        turnOff(i);
    }
}

void doSwap () {
    FOR(i, 0, n/2 - 1) {
        swap(a[i], a[n-i-1]);
        swap(to[i], to[n-i-1]);
    }
    start = n-1-start;
}

long long int findMaxAttraction(int N, int st, int d, int attraction[]) {
    n = N;
    start = st;
    FOR(i, 0, n-1) a[i] = attraction[i];

    FOR(i, 0, n-1) {
        srt.pb({a[i], i});
    }
    sort(srt.begin(), srt.end());
    reverse(srt.begin(), srt.end());

    FOR(i, 0, n-1) {
        to[srt[i].s] = i;
    }

    ll ans = 0;

    REP(2) {

        FOR(i, 0, d) {
            ansF[i] = ansG[i] = 0;
            f[i] = start;
            g[i] = start-1;
        }

        build ();

        doSwap();
        if (start+1 <= n-1) rec(0, d, start+1, n-1);
        doSwap();
       /* FOR(i, 0, d) {
            cout << " i = " << i  << endl;
            cout << "  f(i) = " << f[i] << " ansF(i) = " << ansF[i] << endl;
            cout << "  g(i) = " << g[i] << " ansG(i) = " << ansG[i] << endl;
        } */

        FOR(i, 0, d) f[i] = n-1-f[i];
        FOR(i, 0, d) {
            g[i] = f[i];
            ansG[i] = ansF[i];
        }

        build ();
        FOR(i, 0, d) {
            ansF[i] = 0;
            f[i] = start;
        }

        rec(0, d, start, n-1);

        FOR(d0, 0, d) {
            int rem = d - d0 - (f[d0]-start) - 1;
            if (rem < 0) break;
            ll cur = ansF[d0] + ansG[rem];
            ans = max(ans, cur);
        }

       /* FOR(i, 0, d) {
            cout << " i = " << i  << endl;
            cout << "  f(i) = " << f[i] << " ansF(i) = " << ansF[i] << endl;
            cout << "  g(i) = " << g[i] << " ansG(i) = " << ansG[i] << endl;
        } */

        doSwap();
    }

    //FOR(i, 0, d) cout << " i = " << i << " f(i) = " << f[i] << " ansF(i) = " << ansF[i] << endl;

    return ans;
}

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