Submission #542635

#	Time	Username	Problem	Language	Result	Execution time	Memory
542635		alextodoran	Holiday (IOI14_holiday)	C++17	100 / 100	1816 ms	5956 KiB

holiday

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = (int) 1e5;

int n;
int start, days;
int attr[N_MAX];

int chng = 0;

struct Segment {
    int l, r;
    multiset <int> take, skip;
    int cntTake;
    ll sumTake;
    Segment () {
        l = 1, r = 0;
        sumTake = 0;
    }
    void fix () {
        cntTake = max(0, days - abs(start - l) - (r - l));
        while (take.empty() == false && skip.empty() == false) {
            int minTake = *take.begin();
            int maxSkip = *prev(skip.end());
            if (minTake < maxSkip) {
                sumTake -= minTake;
                take.erase(take.begin());
                skip.erase(prev(skip.end()));
                sumTake += maxSkip;
                take.insert(maxSkip);
                skip.insert(minTake);
            } else {
                break;
            }
        }
        while ((int) take.size() > cntTake) {
            sumTake -= *take.begin();
            skip.insert(*take.begin());
            take.erase(take.begin());
        }
        while ((int) take.size() < cntTake && skip.empty() == false) {
            sumTake += *prev(skip.end());
            take.insert(*prev(skip.end()));
            skip.erase(prev(skip.end()));
        }
    }
    void addL () {
        skip.insert(attr[--l]);
        fix();
    }
    void addR () {
        skip.insert(attr[++r]);
        fix();
    }
    void cutL () {
        if (skip.find(attr[l]) != skip.end()) {
            skip.erase(skip.find(attr[l]));
        } else {
            sumTake -= attr[l];
            take.erase(take.find(attr[l]));
        }
        l++;
        fix();
    }
    void cutR () {
        if (skip.find(attr[r]) != skip.end()) {
            skip.erase(skip.find(attr[r]));
        } else {
            sumTake -= attr[r];
            take.erase(take.find(attr[r]));
        }
        r--;
        fix();
    }
    void moveTo (int L, int R) {
        while (L < l) {
            addL();
        }
        while (r < R) {
            addR();
        }
        while (l < L) {
            cutL();
        }
        while (R < r) {
            cutR();
        }
    }
};

Segment seg;

ll solve (int l1, int l2, int r1, int r2) {
    int l = (l1 + l2) / 2;
    seg.moveTo(l, max(l, r1));
    int r = r1; ll maxSum = 0;
    for (int i = max(l, r1); i <= r2; i++) {
        seg.moveTo(l, i);
        if (seg.sumTake > maxSum) {
            maxSum = seg.sumTake;
            r = i;
        }
    }
    if (l1 <= l - 1) {
        maxSum = max(maxSum, solve(l1, l - 1, r1, r));
    }
    if (l + 1 <= l2) {
        maxSum = max(maxSum, solve(l + 1, l2, r, r2));
    }
    return maxSum;
}

ll findMaxAttraction (int _n, int _start, int _days, int _attr[]) {
    n = _n;
    start = _start;
    days = _days;
    for (int i = 0; i < n; i++) {
        attr[i] = _attr[i];
    }
    ll answer = solve(0, start, start, n - 1);
    reverse(attr, attr + n);
    seg = Segment();
    start = (n - 1) - start;
    answer = max(answer, solve(0, start, start, n - 1));
    return answer;
}

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