Submission #1165334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165334		BlockOG	Holiday (IOI14_holiday)	C++20	0 / 100	5092 ms	5892 KiB

holiday

#include "holiday.h"
#include <algorithm>
#include <iostream>
#include <utility>

// meow mrrow nya nya :3c
// play vivid/stasis. free on steam

using namespace std;

const int N = 1 << 17;

pair<long long, int> sg1[N * 2];
pair<int, int> so1[N];
int rs1[N];
int fs[N * 3];
long long fsv[N * 3];

pair<long long, int> sg2[N * 2];
pair<int, int> so2[N];
int rs2[N];
int gs[N * 3];
long long gsv[N * 3];

void set_ac1(int i, bool v) {
    i += N;
    sg1[i].second = v;
    i /= 2;
    sg1[i].first = sg1[i * 2].first * sg1[i * 2].second + sg1[i * 2 + 1].first * sg1[i * 2 + 1].second;
    sg1[i].second = sg1[i * 2].second + sg1[i * 2 + 1].second;
    for (i /= 2; i > 0; i /= 2)
        sg1[i].first = sg1[i * 2].first + sg1[i * 2 + 1].first, sg1[i].second = sg1[i * 2].second + sg1[i * 2 + 1].second;
}

void set_ac2(int i, bool v) {
    i += N;
    sg2[i].second = v;
    i /= 2;
    sg2[i].first = sg2[i * 2].first * sg2[i * 2].second + sg2[i * 2 + 1].first * sg2[i * 2 + 1].second;
    sg2[i].second = sg2[i * 2].second + sg2[i * 2 + 1].second;
    for (i /= 2; i > 0; i /= 2)
        sg2[i].first = sg2[i * 2].first + sg2[i * 2 + 1].first, sg2[i].second = sg2[i * 2].second + sg2[i * 2 + 1].second;
}

pair<long long, int> lx1(int x, int i = 1) {
    if (sg1[i].second <= x) {
        if (i >= N) return {sg1[i].first * sg1[i].second, sg1[i].second};
        return sg1[i];
    }

    pair<long long, int> l = lx1(x, i * 2);
    if (l.second < x) {
        pair<long long, int> r = lx1(x - l.second, i * 2 + 1);
        l.first += r.first, l.second += r.second;
    }

    return l;
}

pair<long long, int> lx2(int x, int i = 1) {
    if (sg2[i].second <= x) {
        if (i >= N) return {sg2[i].first * sg2[i].second, sg2[i].second};
        return sg2[i];
    }

    pair<long long, int> l = lx2(x, i * 2);
    if (l.second < x) {
        pair<long long, int> r = lx2(x - l.second, i * 2 + 1);
        l.first += r.first, l.second += r.second;
    }

    return l;
}

int f(int d, int l, int r) {
    int mi = 0;
    long long m = 0;
    for (int i = l; i < r && d - i > 0; i++) {
        set_ac1(rs1[i], true);
        long long c = lx1(d - i).first;
        if (c > m) m = c, mi = i;
    }

    fs[d] = mi;
    fsv[d] = m;

    return mi;
}

int g(int d, int l, int r) {
    int mi = 0;
    long long m = 0;
    for (int i = l; i < r && d - i > 0; i++) {
        set_ac2(rs2[i], true);
        long long c = lx2(d - i).first;
        if (c > m) m = c, mi = i;
    }

    gs[d] = mi;
    gsv[d] = m;

    return mi;
}

void recf(int ml, int mr, int l, int r) {
    int mm = (ml + mr) / 2;
    f(mm, l, r);
    if (ml == mr) return;

    for (int i = l; i < r; i++) set_ac1(i, false);
    if (mm - 1 >= ml) recf(ml, mm - 1, l, fs[mm] + 1);
    for (int i = 0; i <= fs[mm]; i++) set_ac1(i, true);
    if (mm + 1 <= mr) recf(mm + 1, mr, fs[mm], r);
}

void recg(int ml, int mr, int l, int r) {
    int mm = (ml + mr) / 2;
    g(mm, l, r);
    if (ml == mr) return;

    for (int i = l; i < r; i++) set_ac2(i, false);
    if (mm - 1 >= ml) recg(ml, mm - 1, l, gs[mm] + 1);
    for (int i = 0; i <= gs[mm]; i++) set_ac2(i, true);
    if (mm + 1 <= mr) recg(mm + 1, mr, gs[mm], r);
}

long long findMaxAttraction(int n, int start, int d, int attraction[]) {
    int n1 = n - start;
    int n2 = start;

    for (int i = 0; i < n1; i++) so1[i].first = attraction[n2 + i], so1[i].second = i;
    sort(so1, so1 + n1, [](pair<int, int> a, pair<int, int> b) { return a.first > b.first; });
    for (int i = 0; i < n1; i++) sg1[N + i].first = so1[i].first, rs1[so1[i].second] = i;

    for (int i = 0; i < n2; i++) so2[n2 - i - 1].first = attraction[i], so2[i].second = i;
    sort(so2, so2 + n2, [](pair<int, int> a, pair<int, int> b) { return a.first > b.first; });
    for (int i = 0; i < n2; i++) sg2[N + i].first = so2[i].first, rs2[so2[i].second] = i;

    recf(1, d, 0, n1);
    recg(1, d, 0, n2);

    long long res = gsv[d - 1];
    for (int d0 = 0; d0 <= d; d0++) {
        int g0 = d - d0 - fs[d0] - 1;
        long long nres = fsv[d0] + (g0 > 0 ? gsv[g0] : 0);
        if (nres > res) res = nres;
    }

    return res;
}

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