Submission #392027

#	Time	Username	Problem	Language	Result	Execution time	Memory
392027		Aldas25	Holiday (IOI14_holiday)	C++14	23 / 100	50 ms	7660 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) {
    turn (1, p);
}

void turnOff (int 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);
}

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

    ll ans = 0;

    FOR(i, 0, n-1) {
        if (d-i <= 0) break;
        turnOn(to[i]);
       // cout << " i = " << i << endl;
       // cout << "  turned on " << to[i] << endl;
        ll cur = get(d-i);
       // cout << "  cur = " << cur << endl;
        ans = max(ans, cur);
    }

    return ans;
}

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