Submission #744719

#	Time	Username	Problem	Language	Result	Execution time	Memory
744719		PixelCat	Holiday (IOI14_holiday)	C++14	100 / 100	1394 ms	7164 KiB

holiday

#include"holiday.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 100010;

int a[MAXN];

int solve1(int n, int st, int d) {
    int sum = 0;
    priority_queue<int, vector<int>, greater<int>> pq;
    int res = 0;
    For(i, st, min(st + d, n - 1)) {
        sum += a[i];
        pq.emplace(a[i]);
        while(sz(pq) + (i - st) > d) {
            sum -= pq.top();
            pq.pop();
        }
        res = max(res, sum);
    }
    return res;
}

struct Ayaya {
    int ss, sb;
    multiset<int> smol, big;
    int l, r;
    void init(int st) {
        ss = sb = 0;
        smol.clear();
        big.clear();
        l = st; r = st;
        add(a[st]);
    }
    void add(int x) {
        if(sz(big) && x >= *big.begin()) {
            sb += x;
            big.insert(x);
        } else {
            ss += x;
            smol.insert(x);
        }
    }
    void erase(int x) {
        if(sz(big) && x >= *big.begin()) {
            sb -= x;
            big.erase(big.find(x));
        } else {
            ss -= x;
            smol.erase(smol.find(x));
        }
    }
    void update(int nl, int nr) {
        while(l > nl) { l--; add(a[l]); }
        while(l < nl) { erase(a[l]); l++; }
        while(r > nr) { erase(a[r]); r--; }
        while(r < nr) { r++; add(a[r]); }
        if(sz(big) + sz(smol) != r - l + 1) exit(0);
        if(sz(big) && sz(smol) && (*big.begin()) < (*prev(smol.end()))) exit(0);
    }
    int ask(int k) {
        if(k <= 0) return 0;
        if(k >= r - l + 1) return ss + sb;
        while(sz(big) < k) {
            int x = *prev(smol.end());
            ss -= x; sb += x;
            smol.erase(prev(smol.end()));
            big.insert(x);
        }
        while(sz(big) > k) {
            int x = *big.begin();
            sb -= x; ss += x;
            big.erase(big.begin());
            smol.insert(x);
        }
        return sb;
    }
    void out() {
        cout << ss << " " << sb << ":";
        for(auto &i:smol) cout << " " << i;
        for(auto &i:big) cout << " " << i;
        cout << "\n" << flush;
    }
} aya;

// divide & conquer
int src[MAXN];
int dnc(int il, int ir, int jl, int jr, int st, int d) {
    if(il > ir) return 0;

    int res = 0;
    int im = (il + ir) / 2;
    
    int mx = -1, mxj = -1;
    For(j, jl, jr) {
        aya.update(im, j);
        int val = aya.ask(d - (st - im) * 2 - (j - st));
        if(val > mx) {
            mx = val; mxj = j;
        }
    }
    res = mx;
    src[im] = mxj;

    res = max(res, dnc(il, im - 1, jl, mxj, st, d));
    res = max(res, dnc(im + 1, ir, mxj, jr, st, d));
    return res;
}

int solve2(int n, int st, int d) {
    aya.init(st);
    int res = dnc(0, st, st, n - 1, st, d);
    return res;
}

LL findMaxAttraction(int32_t n, int32_t start, int32_t d, int32_t attractions[]) {
    For(i, 0, n - 1) a[i] = attractions[i];
    int res = 0;
    For(phase, 0, 1) {
        res = max(res, solve1(n, start, d));
        res = max(res, solve2(n, start, d));
        reverse(a, a + n);
        start = n - 1 - start;
    }
    return res;
}

/*

60
4436
334588796671
3389595012736

*/

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