oj.uz

Submission #423086

# Submission time Handle Problem Language Result Execution time Memory
423086 2021-06-10T17:14:31 Z ocarima Holiday (IOI14_holiday) C++14
0 / 100
 5000 ms 6924 KB 
#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;

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;

    // INICIALIZA EL SEGMENT TREE
    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;
            }
        }
    }

    return optr[d];
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5060 ms 6812 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 6924 KB Output isn't correct
2 Halted 0 ms 0 KB -