Submission #105058

#	Time	Username	Problem	Language	Result	Execution time	Memory
105058		alexpetrescu	Holiday (IOI14_holiday)	C++14	100 / 100	1609 ms	15732 KiB

holiday

#include"holiday.h"
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>

#define vec std::vector
#define myc std::pair < int, int >
#define x first
#define y second

#define ll long long

#define MAXN 100000
#define MAXP 265000

struct node {
    int cnt;
    ll sum;
} aint[MAXP];
ll val;
int poz, cnt;

void update(int p, int st, int dr) {
    if (st == dr) {
        aint[p].cnt = val > 0;
        aint[p].sum = val;
    } else {
        int m = (st + dr) / 2;
        if (poz <= m) update(2 * p, st, m);
        else update(2 * p + 1, m + 1, dr);
        aint[p].cnt = aint[2 * p].cnt + aint[2 * p + 1].cnt;
        aint[p].sum = aint[2 * p].sum + aint[2 * p + 1].sum;
    }
}

void query(int p, int st, int dr) {
    if (poz != dr + 1)
        return ;
    if (aint[p].cnt <= cnt) {
        cnt -= aint[p].cnt;
        val += aint[p].sum;
        poz = st;
        return ;
    }
    if (st == dr)
        return ;
    int m = (st + dr) / 2;
    query(2 * p + 1, m + 1, dr);
    query(2 * p, st, m);
}

void divide(int cost, vec < myc > &V, vec < ll > &dp, int left, int right, int st, int dr, int &unde) {
    if (left > right)
        return ;
    while (unde < st) {
        unde++;
        poz = V[unde].y;
        val = V[unde].x;
        update(1, 0, V.size() - 1);
    }
    while (unde > st) {
        poz = V[unde].y;
        val = 0;
        update(1, 0, V.size() - 1);
        unde--;
    }
    int sol = st, m = (left + right) / 2;
    poz = V.size();
    val = 0;
    cnt = m - cost * st - cost;
    query(1, 0, V.size() - 1);
    dp[m] = val;
    for (int i = st + 1; i <= dr; i++) {
        unde++;
        poz = V[unde].y;
        val = V[unde].x;
        update(1, 0, V.size() - 1);

        poz = V.size();
        val = 0;
        cnt = m - cost * i - cost;
        query(1, 0, V.size() - 1);
        if (val > dp[m]) {
            sol = i;
            dp[m] = val;
        }
    }
    divide(cost, V, dp, left, m - 1, st, sol, unde);
    divide(cost, V, dp, m + 1, right, sol, dr, unde);
}

inline void solve(int cost, vec < ll > &dp, vec < int > &v) {
    if (v.empty())
        return ;
    memset(aint, 0, sizeof aint);
    vec < myc > W(v.size()), V(v.size());
    for (int i = 0; i < (int)v.size(); i++)
        W[i] = {v[i], i};
    std::sort(W.begin(), W.end());
    for (int i = 0; i < (int)V.size(); i++)
        V[W[i].y] = {W[i].x, i};
    int unde = -1;
    divide(cost, V, dp, 0, dp.size() - 1, 0, v.size() - 1, unde);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    vec < ll > left1(d + 1, 0), left2(d + 1, 0), right1(d + 1, 0), right2(d + 1, 0);
    vec < int > st, dr;
    for (int i = start - 1; i >= 0; i--)
        st.push_back(attraction[i]);
    for (int i = start + 1; i < n; i++)
        dr.push_back(attraction[i]);
    solve(1, left1, st);
    solve(2, left2, st);
    solve(1, right1, dr);
    solve(2, right2, dr);

    ll ans = 0;
    for (int i = 0; i <= d; i++)
        ans = std::max(ans, std::max(left2[i] + right1[d - i], right2[i] + left1[d - i]));
    for (int i = 0; i < d; i++)
        ans = std::max(ans, attraction[start] + std::max(left2[i] + right1[d - i - 1], right2[i] + left1[d - i - 1]));
    return ans;
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

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