Submission #423102

#	Time	Username	Problem	Language	Result	Execution time	Memory
423102		ocarima	Holiday (IOI14_holiday)	C++14	0 / 100	5082 ms	6672 KiB

holiday

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

using namespace std;

#define debugsl(x) cout << #x << " = " << x << ", "
#define debug(x) debugsl(x) << "\n"

#define lli long long
#define rep(i, a, b) for(lli i = (a); i <= (b); ++i)

#define MAX_N 100003

#define atracciones first
#define pos second

#define activas first
#define suma second

int lugar[MAX_N], offset, tmp;
vector<pair<int, int> > sortedatt;
pair<lli, lli> st[1 << 18];
lli optr[MAX_N * 2], optl[MAX_N * 2], maxr[MAX_N * 2], maxl[MAX_N * 2], res, avl, avr;

lli queryst(int nodo, int k){
    if (!k) return 0;
    if (st[nodo].activas <= k) return st[nodo].suma;
    if (st[nodo * 2].activas > k) return queryst(nodo * 2, k);
    else return st[nodo * 2].suma + queryst(nodo * 2 + 1, k - st[nodo * 2].activas);
}

void updatest(int p){
    st[offset + p].activas = 1;
    st[offset + p].suma = sortedatt[p].atracciones;
    p += offset;

    while (p > 0){
        p >>= 1;
        st[p].activas = st[p * 2].activas + st[p * 2 + 1].activas;
        st[p].suma = st[p * 2].suma + st[p * 2 + 1].suma;
    }
}

void initst(){
    rep(i, 0, offset * 2 - 1) st[i] = {0,0};
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {

    rep(i, 0, n - 1) sortedatt.emplace_back(attraction[i], i);
    sort(sortedatt.begin(), sortedatt.end());
    reverse(sortedatt.begin(), sortedatt.end());

    rep(i, 0, n - 1) lugar[sortedatt[i].pos] = i;

    offset = 1;
    while (offset < n) offset <<= 1;

    initst();
    rep(ciudad, 0, n - start + 1){
        updatest(lugar[start + ciudad]);
        rep(att, 1, min(ciudad + 1, (lli)d)){
            tmp = queryst(1, att);
            if (tmp > optr[ciudad + att]){
                optr[ciudad + att] = tmp;
                maxr[ciudad + att] = ciudad;
            }
        }
    }

    initst();
    rep(ciudad, 1, start){
        updatest(lugar[start - ciudad]);
        rep(att, 1, min(ciudad + 1, (lli)d)){
            tmp = queryst(1, att);
            if (tmp > optl[ciudad + att]){
                optl[ciudad + att] = tmp;
                maxl[ciudad + att] = ciudad;
            }
        }
    }

    res = 0;
    rep(i, 0, d){
        // si va primero a la izquierda
        avl = maxl[i] + i;
        if (avl <= d) res = max(res, optl[i] + optr[d - avl]);

        // si va primero a la derecha
        avr = maxr[i] + i;
        if (avr <= d) res = max(res, optr[i] + optl[d - avr]);
    }

    return res;
}

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