Submission #1161944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161944		InvMOD	Holiday (IOI14_holiday)	C++20	24 / 100	336 ms	25592 KiB

holiday

#include<bits/stdc++.h>

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

using namespace std;

#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define dbg(x) "[" << #x "=" << (x) << "]"

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;

struct Node{
    ll sum; int cnt;
    Node(ll sum = 0, int cnt = 0): sum(sum), cnt(cnt) {}

    Node operator + (const Node& q) const{
        return Node(sum + q.sum, cnt + q.cnt);
    }
};

int n, start, vstart, d, a[N], ptr;

ll answer, dp[2][N], opt[2][N];

Node st[N << 2];

vector<int> comp;

void update(int id, int l, int r, int x, int val){
    if(l == r){
        st[id].cnt += val;
        st[id].sum = 1ll * st[id].cnt * comp[l];
    }
    else{
        int m = l+r>>1;
        if(x <= m){
            update(id << 1, l, m, x, val);
        }
        else{
            update(id << 1|1, m+1, r, x, val);
        }
        st[id] = st[id << 1] + st[id << 1|1];
    }
}

ll get(int id, int l, int r, int k){
    if(st[id].cnt <= k){
        return st[id].sum;
    }

    int m = l+r>>1;
    if(st[id << 1|1].cnt >= k){
        return get(id << 1|1, m+1, r, k);
    }
    return get(id << 1, l, m, k - st[id << 1|1].cnt) + st[id << 1|1].sum;
}


int cntCheck[N];
void Dnc(int l, int r, int optL, int optR, int t){
    if(l > r || optL > optR) return;
    // Update
    assert(optL <= optR);
    for(; ptr + 1 < optL; ptr++){
        cntCheck[ptr + 1]++;
        update(1, 1, n, a[ptr + 1], +1);
    }

    for(; ptr >= optL; ptr--){
            cntCheck[ptr]--;
        update(1, 1, n, a[ptr], -1);
    }

    int mid = l+r>>1;

    ll curDP = 0, best = optL;

    assert(ptr == optL - 1);
    for(++ptr; ptr <= optR; ptr++){
        cntCheck[ptr]++;
        update(1, 1, n, a[ptr], +1);

        // mid day -> number we can choose = mid - (p - start)
        int choose = mid - (ptr - start);

        if(choose <= 0){
            ptr++;
            break;
        }
        if(ckmx(curDP, get(1, 1, n, choose))){
            best = ptr;
        }
    }
    --ptr;

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

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


void process()
{
    ptr = start - 1;
    opt[0][0] = start;
    opt[1][0] = start - 1;
    Dnc(1, d, start, n, 0);

    for(; ptr >= start; ptr--){
            cntCheck[ptr]--;
        update(1, 1, n, a[ptr], -1);
    }
    reverse(a + 1, a + 1 + n);
    assert(st[1].sum == 0);
//    for(int i = 1; i <= n; i++){
//        cout << a[i] <<" ";
//    } cout << "\n";

    start = n - start + 1;
    ptr = start;

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

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

//    for(int j = 0; j < 2; j++){
//        for(int i = 0; i <= d; i++){
//            cout << dbg(opt[j][i]) << dbg(dp[j][i]) << "\n";
//        } cout << "\n";
//    }

    auto dist = [&](int first, int last) -> int{
        return abs(start - first) + abs(last - first);
    };

    for(int i = 0, j = d; i <= d; i++){
        while(j >= 1 && i + j + abs(start - opt[0][i]) > d){
            j--;
        }
        if(j > 0)
            answer = max(answer, dp[0][i] + dp[1][j]);
        answer = max(answer, dp[0][i]);
    }

    for(int i = 0, j = d; i <= d; i++){
        while(j >= 1 && i + j + abs(start - opt[1][i]) > d){
            j--;
        }
        if(j > 0)
            answer = max(answer, dp[1][i] + dp[0][j]);
        answer = max(answer, dp[1][i]);
    }
}

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

    n = _n, d = _d;
    for(int i = 1; i <= n; i++){
        a[i] = attraction[i - 1];
        comp.push_back(a[i]);
    }
    comp.push_back(-1);

    sort(all(comp)); compact(comp);
    for(int i = 1; i <= n; i++){
        a[i] = lower_bound(all(comp), a[i]) - comp.begin();
    }

    process();

    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";
        return 0;
    }
#endif // name

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