제출 #1162277

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162277		InvMOD	Holiday (IOI14_holiday)	C++20	23 / 100	494 ms	13744 KiB

holiday

#include<bits/stdc++.h>

//#define name "InvMOD"
#ifndef name
    #include "holiday.h"
#endif // name

using namespace std;

#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()

using ll = long long;

template<typename T> bool ckmx(T& a, const T& b){
    if(a < b)
        return a = b, true;
    return false;
}

const int N = 3e5 + 5;

int n, d, start, ptr, opt[2][N];

ll a[N], val[N], st[N << 2][2], dp[2][N];

void apply(int id, int l){
    st[id][0] = 1 - st[id][0];
    st[id][1] = val[l] * st[id][0];
}

void merge_st(int id){
    st[id][0] = st[id << 1][0] + st[id << 1|1][0];
    st[id][1] = st[id << 1][1] + st[id << 1|1][1];
}

void update(int id, int l, int r, int x){
    if(l == r){
        apply(id, l);
    }
    else{
        int m = l+r>>1;
        if(x <= m)
            update(id << 1, l, m, x);
        else update(id << 1|1, m+1, r, x);
        merge_st(id);
    }
}

void upd(int x){
    update(1, 1, n, a[x]);
}

ll get(int id, int l, int r, int target){
    if(!st[id][0] || target <= 0) return 0ll;

    if(st[id][0] <= target) return st[id][1];

    // st[id][0] > target -> prioritize [m + 1 -> r]

    int m = l + r >> 1;
    if(st[id << 1|1][0] >= target){
        return get(id << 1|1, m+1, r, target);
    }

    int ntarget = target - st[id << 1|1][0];
    return st[id << 1|1][1] + get(id << 1, l, m, ntarget);
}

ll query(int target){
    return get(1, 1, n, target);
}

void resetST(){
    for(int id = 1; id <= (n << 2) + 5; id++){
        st[id][0] = 0;
        st[id][1] = 0;
    }
}

void Dnc(int l, int r, int optL, int optR, int t){
    if(l > r) return;

    for(; ptr < optL; ptr++) upd(ptr);
    for(; ptr > optL; ptr--) upd(ptr - 1);

    int mid = l+r>>1;

    ll best = 0, optPos = optL;
    for(; ptr <= optR; ptr++){
        upd(ptr);

        int choose = mid - (ptr - start);
        if(choose < 0) continue;

        if(ckmx(best, query(choose))){
            optPos = ptr;
        }
    }

    dp[t][mid] = best;
    opt[t][mid] = optPos;

    Dnc(l, mid - 1, optL, optPos, t);
    Dnc(mid + 1, r, optPos, optR, t);
}

ll findMaxAttraction(int _n, int _start, int _d, int attraction[]){
    n = _n, start = _start + 1, d = _d;

    vector<int> idx(n + 1);
    for(int i = 1; i <= n; i++){
        a[i] = attraction[i - 1];
        idx[i] = i;
    }
    sort(1 + all(idx), [&](int x, int y){return a[x] < a[y];});

    for(int i = 1; i <= n; i++){
        val[i] = a[idx[i]];
        a[idx[i]] = i;
    }

    ptr = start;
    Dnc(0, d, start, n, 0);

    resetST();
    start = n - start + 1;
    reverse(a + 1, a + 1 + n);

    ptr = start + 1;
    Dnc(1, d, start + 1, n, 1);

    start = n - start + 1;
    for(int i = 1; i <= d; i++){
        opt[1][i] = n - opt[1][i] + 1;
    }


    ll answer = 0;
    for(int i = 0; i <= d; i++){
        int need = i + (opt[0][i] - start);
        if(need <= d)
            ckmx(answer, dp[0][i] + dp[1][d - need]);
        ckmx(answer, dp[0][i]);
    }

    for(int i = 1; i <= d; i++){
        int need = i + (start - opt[1][i]);
        if(need <= d)
            ckmx(answer, dp[1][i] + dp[0][d - need]);
        ckmx(answer, dp[1][i]);
        if(i < d) ckmx(answer, dp[1][i] + val[a[start]]); // bruh-wtf InvMOD so dumb
    }
    return answer;
}

#ifdef name
    int32_t main()
    {
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);

        int n,start,d; cin >> n >> start >> d;

        int attraction[n];
        for(int i = 0; i < n; i++){
            cin >> attraction[i];
        }

        cout << findMaxAttraction(n, start, d, attraction) << "\n";
    }

#endif // name

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