Submission #170634

#	Time	Username	Problem	Language	Result	Execution time	Memory
170634		DS007	Holiday (IOI14_holiday)	C++14	24 / 100	158 ms	65540 KiB

holiday

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

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

    node() {
        val = size = 0;
        left = nullptr;
        right = nullptr;
    }
};

const int NN = 1e5, DD = 2 * NN + NN / 2;
map<long long, long long> m1, m2;
node* v[NN + 1];
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(node *cur, node *prev, int tl, int tr, int l) {
    if (l == tl && tl == tr) {
        cur->val = prev->val + m2[l];
        cur->size = prev->size + 1;
        return;
    }

    int tm = (tl + tr) / 2;
    if (l <= tm) {
        cur->right = prev->right;
        cur->left = new node();
        update(cur->left, prev->left, tl, tm, l);
    } else {
        cur->left = prev->left;
        cur->right = new node();
        update(cur->right, prev->right, tm + 1, tr, l);
    }

    cur->val = cur->left->val + cur->right->val;
    cur->size = cur->left->size + cur->right->size;
}

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

    n->left = new node();
    n-> right = new node();
    int tm = (tl + tr) / 2;
    build(n->left, tl, tm);
    build(n->right, tm + 1, tr);
}

void build() {
    v[0] = new node();
    build(v[0], 0, N - 1);

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

long long query(node *n1, node *n2, int tl, int tr, int c) {
    c = min(c, n2->size - n1->size);
    if (c <= 0)
        return 0;

    if (n2->size - n1->size == c)
        return n2->val - n1->val;

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

    int tm = (tl + tr) / 2;
    if (n2->right->size - n1->right->size >= c)
        return query(n1->right, n2->right, tm + 1, tr, c);
    else
        return query(n1->right, n2->right, tm + 1, tr, n2->right->size - n1->right->size) + query(n1->left, n2->left, tl, tm, c - (n2->right->size - 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]);
    }
    printf("%lld\n", findMaxAttraction(n, start, d,  attraction));
    return 0;
}*/

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