제출 #1162179

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162179		InvMOD	Holiday (IOI14_holiday)	C++20	100 / 100	473 ms	14888 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 dbg_ST(int id, int l, int r, int x, int wv){
//    if(l == r){
//        if(st[id][1] != wv){
//            cout << "DBG ST:\n";
//            cout << l <<" " << ptr <<"\n" << wv << " " << st[id][1] <<" " << val[l] << "\n";
//
//            exit(0);
//        }
//    }
//    else{
//        int m = l+r>>1;
//        if(x <= m)
//            dbg_ST(id << 1, l, m, x, wv);
//        else dbg_ST(id << 1|1, m+1, r, x, wv);
//        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){
    /*
    if(ptr < start){
        for(int i = ptr; i < start; i++){
            dbg_ST(1, 1, n, a[i], val[a[i]]);
        }

        for(int i = 1; i < ptr; i++){
            dbg_ST(1, 1, n, a[i], 0);
        }

        for(int i = start; i <= n; i++){
            dbg_ST(1, 1, n, a[i], 0);
        }

        vector<int> vec;
        for(int i = ptr; i < start; i++){
            vec.push_back(val[a[i]]);
        }
        sort(all(vec));

        ll sum = 0;
        for(int i = vec.size() - 1; i >= max(0, (int)vec.size() - target); i--){
            sum += 1ll * vec[i];
        }

        if(sum != get(1, 1, n, target)){
            cout << sum <<" " << ptr <<" " << target << "\n";
            cout << get(1, 1, n, target) << "\n";

            exit(0);
        }
        return sum;
    }
    else{
        for(int i = start; i <= ptr; i++){
            dbg_ST(1, 1, n, a[i], val[a[i]]);
        }

        for(int i = 1; i < start; i++){
            dbg_ST(1, 1, n, a[i], 0);
        }

        for(int i = ptr + 1; i <= n; i++){
            dbg_ST(1, 1, n, a[i], 0);
        }

        vector<int> vec;
        for(int i = start; i <= ptr; i++){
            vec.push_back(val[a[i]]);
        }
        sort(all(vec));

        ll sum = 0;
        for(int i = vec.size() - 1; i >= max(0, (int)vec.size() - target); i--){
            sum += 1ll * vec[i];
        }

        if(sum != get(1, 1, n, target)){
            cout << sum <<" " << ptr <<" " << target << "\n";
            cout << get(1, 1, n, target) << "\n";

            exit(0);
        }
        return sum;
    }
    */

    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_Up(int l, int r, int optL, int optR){
    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[0][mid] = best;
    opt[0][mid] = optPos;

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

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

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

    int mid = l+r>>1;

    ll best = 0, optPos = optR;
    for(; ptr >= optL; ptr--){
        upd(ptr);

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

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

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

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

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_Up(0, d, start, n);
    if(start == 1){
        return dp[0][d];
    }

    resetST();

    ptr = start - 1;
    Dnc_Down(1, d, 1, start - 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: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53