Submission #575862

#	Time	Username	Problem	Language	Result	Execution time	Memory
575862		2fat2code	Holiday (IOI14_holiday)	C++17	100 / 100	1860 ms	15128 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
#define fr first
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sc second
#define all(s) s.begin(), s.end()
#define rc(s) return cout << s, 0
using namespace std;

const int nmax = 100005;
const int dmax = 300005;

long long n, nn, start, d, curr, dp[4][dmax];
vector<long long>compress;
pair<long long, long long>tree[4 * nmax];

void update(int l, int r, int pos, pair<long long, long long>val, int nod){
    if(l == r){
        if(val.sc == 1LL) tree[nod].fr += val.fr;
        else tree[nod].fr -= val.fr;
        tree[nod].sc += val.sc;
    }
    else{
        int mid = l + (r - l) / 2;
        if(pos <= mid) update(l, mid, pos, val, 2*nod);
        else update(mid+1, r, pos, val, 2*nod + 1);
        tree[nod].fr = (tree[2 * nod].fr + tree[2 * nod + 1].fr);
        tree[nod].sc = (tree[2 * nod].sc + tree[2 * nod + 1].sc);
    }
}


long long query(int l, int r, long long nrelemente, int nod){
    if(l == r){
        return compress[l - 1] * min(nrelemente, tree[nod].sc);
    }
    else{
        int mid = l + (r - l) / 2;
        if(tree[2*nod + 1].sc >= nrelemente){
            return query(mid + 1, r, nrelemente, 2*nod + 1);
        }
        else{
            return tree[2*nod + 1].fr + query(l, mid, nrelemente - tree[2*nod+1].sc, 2*nod);
        }
    }
}

void O_o(int l_time, int r_time, int l_interval, int r_interval, long long penalty, vector<long long>&arr, int indx){
    if(r_time < l_time) return;
    else{
        int mid = l_time + (r_time - l_time) / 2;
        long long maxi = -1, position = l_interval;
        for(int i=l_interval;i<=r_interval;i++){
            auto it = lower_bound(all(compress), arr[i]) - compress.begin();
            update(1, nn, it + 1, {compress[it], 1}, 1);
            long long curr = mid - i * penalty;
            if(curr >= 0){
                long long lmao = query(1, nn, curr, 1);
                if(maxi < lmao){
                    maxi = lmao;
                    position = i;
                }
            }
        }
        dp[indx][mid] = maxi;
        for(int i=r_interval;i>=position;i--){
            auto it = lower_bound(all(compress), arr[i]) - compress.begin();
            update(1, nn, it + 1, {compress[it], -1}, 1);
        }
        O_o(mid + 1, r_time, position, r_interval, penalty, arr, indx);
        for(int i=position-1;i>=l_interval;i--){
            auto it = lower_bound(all(compress), arr[i]) - compress.begin();
            update(1, nn, it + 1, {compress[it], -1}, 1);
        }
        O_o(l_time, mid - 1, l_interval, position, penalty, arr, indx);
    }
}

long long findMaxAttraction(int n, int start, int d, int a[]) {
    vector<long long>attraction;
    for(int i=0;i<n;i++) attraction.push_back(a[i]);
    for(auto it : attraction){
        compress.push_back(it);
    }
    compress.push_back(0);
    sort(all(compress));
    compress.resize(unique(all(compress)) - compress.begin());
    nn = (int)compress.size();
    vector<long long>lmao;
    for(int i=start;i<n;i++) lmao.push_back(attraction[i]);
    O_o(0, d, 0, lmao.size() - 1, 1, lmao, 0);
    lmao[0] = 0;
    O_o(0, d, 0, lmao.size() - 1, 2, lmao, 1);
    lmao.clear();
    for(int i=start;i>=0;i--) lmao.push_back(attraction[i]);
    O_o(0, d, 0, lmao.size() - 1, 1, lmao, 2);
    lmao[0] = 0;
    O_o(0, d, 0, lmao.size() - 1, 2, lmao, 3);
    long long ans = 0;
    for(int i=0;i<=d;i++){
        ans = max(ans, dp[0][i] + dp[3][d - i]);
        ans = max(ans, dp[2][i] + dp[1][d - i]);
    }
    return ans; 
}

// 1. Solve the problem
// 2. ???
// 3. Profit!

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