Submission #392039

#	Time	Username	Problem	Language	Result	Execution time	Memory
392039		Aldas25	Holiday (IOI14_holiday)	C++14	0 / 100	291 ms	65540 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 = 100100;

ll a[MAXN];
int n;

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 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);
    }
}

long long int findMaxAttraction(int N, int start, int d, int attraction[]) {
    n = N;
    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;
    }

    build ();

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

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

    ll ans = ansF[d];

    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'll rec(int, int, int, int, int)':
holiday.cpp:111:1: warning: no return statement in function returning non-void [-Wreturn-type]
  111 | }
      | ^

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