Submission #170730

#	Time	Username	Problem	Language	Result	Execution time	Memory
170730		DS007	Holiday (IOI14_holiday)	C++14	47 / 100	451 ms	65540 KiB

holiday

#include <bits/stdc++.h>
#include <holiday.h>
using namespace std;

#define tm (tl + tr) / 2

struct node {
    long long val;
    int size;
    int left, right;

    node() {
        val = size = 0;
        left = right = 0;
    }
} nodes[2000000];

const int NN = 1e5, DD = 2 * NN + NN / 2;
map<long long, long long> m1, m2;
int v[NN + 1];
int con = 0;
int N, START, D, *ATTRACTION;
long long dp1[DD + 1], dp2[DD + 1], dp3[DD + 1], dp4[DD + 1];
// int l1[DD + 1], l2[DD + 1], l3[DD + 1], l4[DD + 1];

void pre() {
    int copy[N];
    for (int i = 0; i < N; i++)
        copy[i] = ATTRACTION[i];
    sort(copy, copy + N);

    set<int> s;
    for (int i = 0, j = 0; i < N; i++) {
        if (s.count(copy[i]))
            continue;
        m1[copy[i]] = j;
        m2[j++] = copy[i];
    }
}

void update(int cur, int prev, int tl, int tr, int l) {
    if (l == tl && tl == tr) {
        nodes[cur].val = nodes[prev].val + m2[l];
        nodes[cur].size = nodes[prev].size + 1;
        return;
    }

    // int tm = (tl + tr) / 2;
    if (l <= tm) {
        nodes[cur].right = nodes[prev].right;
        nodes[cur].left = con++;
        update(nodes[cur].left, nodes[prev].left, tl, tm, l);
    } else {
        nodes[cur].left = nodes[prev].left;
        nodes[cur].right = con++;
        update(nodes[cur].right, nodes[prev].right, tm + 1, tr, l);
    }

    nodes[cur].val = nodes[nodes[cur].left].val + nodes[nodes[cur].right].val;
    nodes[cur].size = nodes[nodes[cur].left].size + nodes[nodes[cur].right].size;
}

void build(int n, int tl, int tr) {
    if (tl == tr)
        return;

    nodes[n].left = con++;
    nodes[n].right = con++;
    // int tm = (tl + tr) / 2;
    build(nodes[n].left, tl, tm);
    build(nodes[n].right, tm + 1, tr);
}

void build() {
    v[0] = con++;
    build(v[0], 0, N - 1);

    for (int i = 1; i <= N; i++) {
        v[i] = con++;
        update(v[i], v[i - 1], 0, N - 1, m1[ATTRACTION[i - 1]]);
    }
}

long long query(int n1, int n2, int tl, int tr, int c) {
    c = min(c, nodes[n2].size - nodes[n1].size);
    if (c <= 0)
        return 0;

    if (nodes[n2].size - nodes[n1].size == c)
        return nodes[n2].val - nodes[n1].val;

    if (tl == tr)
        return m2[tl] * c;

    // int tm = (tl + tr) / 2;
    if (nodes[nodes[n2].right].size - nodes[nodes[n1].right].size >= c)
        return query(nodes[n1].right, nodes[n2].right, tm + 1, tr, c);
    else
        return query(nodes[n1].right, nodes[n2].right, tm + 1, tr, nodes[nodes[n2].right].size - nodes[nodes[n1].right].size) + query(nodes[n1].left, nodes[n2].left, tl, tm, c - (nodes[nodes[n2].right].size - nodes[nodes[n1].right].size));
}

/*void calc1() {
    dp1[1] = dp1[2] = ATTRACTION[START];
    l1[1] = l1[2] = START;

    for (int i = 3; i <= D; i++) {
        int t = query(v[l1[i - 1]], v[START + 1], i - 2 * (START - l1[i - 1])), j = l1[i - 1] - 1;
        while (j >= 0) {
            int temp = query(v[j], v[START + 1], i - 2 * (START - j));
            if (temp < t)
                break;
            t = temp;
            j--;
        }

        dp1[i] = t;
        l1[i] = j == -1 ? 0 : j;
    }
}*/

void calc1() {
    pair<long long, int> best = {ATTRACTION[START], START};
    for (int i = START - 1; i >= 0; i--)
        best = max(best, {query(v[i], v[START + 1], 0, N - 1, D - 2 * (START - i)), i});
    dp1[D] = best.first;
    // l1[D] = best.second;
    int l = best.second;

    for (int i = D - 1; i >= 0; i--) {
        pair<long long, int> t = {query(v[l], v[START + 1], 0, N - 1, i - 2 * (START - l)), l};
        for (int j = l + 1; j <= START; j++) {
            pair<long long, int> temp = {query(v[j], v[START + 1], 0, N - 1, i - 2 * (START - j)), j};
            if (max(t, temp) == t)
                break;
            t = temp;
        }
        dp1[i] = t.first;
        l = t.second;
    }
}

/*void calc2() {
    dp2[1] = dp2[2] = ATTRACTION[START];
    l2[1] = l2[2] = START;

    for (int i = 3; i <= D; i++) {
        int t = query(v[START], v[l2[i - 1] + 1], i - 2 * (l1[i - 1] - START)), j = l1[i - 1] + 1;
        while (j < N) {
            int temp = query(v[START], v[j + 1], i - 2 * (j - START));
            if (temp < t)
                break;
            t = temp;
            j++;
        }

        dp2[i] = t;
        l2[i] = j == N ? N - 1 : j;
    }
}*/

void calc2() {
    pair<long long, int> best = {ATTRACTION[START], START};
    for (int i = START + 1; i < N; i++)
        best = max(best, {query(v[START], v[i + 1], 0, N - 1, D - 2 * (i - START)), i});
    dp2[D] = best.first;
    // l2[D] = best.second;
    int l = best.second;

    for (int i = D - 1; i >= 0; i--) {
        pair<long long, int> t = {query(v[START], v[l + 1], 0, N - 1, i - 2 * (l - START)), l};
        for (int j = l - 1; j >= START; j--) {
            pair<long long, int> temp = {query(v[START], v[j + 1], 0, N - 1, i - 2 * (j - START)), j};
            if (max(t, temp) == t)
                break;
            t = temp;
        }
        dp2[i] = t.first;
        l = t.second;
    }
}

/*void calc3() {
    dp3[1] = ATTRACTION[START + 1];
    l3[1] = START + 1;

    for (int i = 2; i <= D; i++) {
        int t = query(v[START + 1], v[l3[i - 1] + 1], i - (l3[i - 1] - START - 1)), j = l3[i - 1] + 1;
        while (j < N) {
            int temp = query(v[START + 1], v[j + 1], i - (j - START - 1));
            if (temp < t)
                break;
            t = temp;
            j++;
        }

        dp3[i] = t;
        l3[i] = j == N ? N - 1 : j;
    }
}*/

void calc3() {
    pair<long long, int> best = {ATTRACTION[START + 1], START + 1};
    for (int i = START + 2; i < N; i++)
        best = max(best, {query(v[START + 1], v[i + 1], 0, N - 1, D - (i - START - 1)), i});
    dp3[D] = best.first;
    // l3[D] = best.second;
    int l = best.second;

    for (int i = D - 1; i >= 0; i--) {
        pair<long long, int> t = {query(v[START + 1], v[l + 1], 0, N - 1, i - (l - START - 1)), l};
        for (int j = l - 1; j >= START + 1; j--) {
            pair<long long, int> temp = {query(v[START + 1], v[j + 1], 0, N - 1, i - (j - START - 1)), j};
            if (max(t, temp) == t)
                break;
            t = temp;
        }
        dp3[i] = t.first;
        l = t.second;
    }
}

/*void calc4() {
    dp4[1] = ATTRACTION[START - 1];
    l4[1] = START - 1;

    for (int i = 2; i <= D; i++) {
        int t = query(v[l4[i - 1]], v[START], i - (START - 1 - l4[i - 1])), j = l4[i - 1] - 1;
        while (j >= 0) {
            int temp = query(v[j], v[START], i - (START - 1 - j));
            if (temp < t)
                break;

        }
    }
}*/

void calc4() {
    pair<long long, int> best = {ATTRACTION[START - 1], START - 1};
    for (int i = START - 2; i >= 0; i--)
        best = max(best, {query(v[i], v[START], 0, N - 1, D - (START - 1 - i)), i});
    dp4[D] = best.first;
    // l4[D] = best.second;
    int l = best.second;

    for (int i = D - 1; i >= 0; i--) {
        pair<long long, int> t = {query(v[l], v[START], 0, N - 1, i - (START - 1 - l)), l};
        for (int j = l + 1; j <= START - 1; j++) {
            pair<long long, int> temp = {query(v[j], v[START], 0, N - 1, i - (START - 1 - j)), j};
            if (max(t, temp) == t)
                break;
            t = temp;
        }
        dp4[i] = t.first;
        l = t.second;
    }
}

long long answer() {
    long long ans = max(dp1[D], dp2[D]);
    for (int i = 0; i <= D - 1; i++) {
        ans = max(ans, dp1[i] + dp3[D - i - 1]);
        ans = max(ans, dp2[i] + dp4[D - i - 1]);
    }
    return ans;
}

long long findMaxAttraction(int n, int start, int d, int attraction[]) {
    N = n;
    START = start;
    D = d;
    ATTRACTION = attraction;

    pre();
    build();

    calc1();
    calc2();
    if (START != N - 1)
        calc3();
    if (START)
        calc4();

    return answer();
}

/*int main() {
    int n, start, d;
    int attraction[100000];
    int i, n_s;
    n_s = scanf("%d %d %d", &n, &start, &d);
    for (i = 0 ; i < n; ++i) {
        n_s = scanf("%d", &attraction[i]);
    }
    cout << findMaxAttraction(n, start, d,  attraction) << endl;
    cout << con << endl;
    return 0;
}*/

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