Submission #969587

#	Time	Username	Problem	Language	Result	Execution time	Memory
969587		GrindMachine	Holiday (IOI14_holiday)	C++17	47 / 100	107 ms	52680 KiB

holiday

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

knew beforehand that this problem could be solved with d&c dp optimization (opt[i] <= opt[i+1])

similar problem:
https://oj.uz/problem/view/JOI19_cake3 (copied some of the implementation from here)

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "holiday.h"

vector<int> oa(N);

struct wavelet_tree{
    struct node{
        node *l, *r;
        vector<int> b;
        vector<ll> pref;
    };
 
    node* root;
    int siz;
 
    wavelet_tree(){
 
    }
 
    node* build(vector<int> &a, vector<int> inds, int l, int r){
        if(l > r) return NULL;
        int mid = (l+r) >> 1;
        vector<int> b(sz(inds)+1);
 
        vector<int> la,ra;
        rep(i,sz(inds)){
            int x = a[inds[i]];
            b[i+1] = b[i]+(x <= mid);
            if(x <= mid){
                la.pb(inds[i]);
            }
            else{
                ra.pb(inds[i]);
            }
        }
 
        node* curr = new node();
        curr->b = b;
 
        vector<ll> pref;
        pref.pb(0);
 
        trav(i,inds){
            pref.pb(pref.back()+oa[i]);
        }
 
        curr->pref = pref;
 
        if(l != r){         
            curr->l = build(a,la,l,mid);
            curr->r = build(a,ra,mid+1,r);
        }
 
        return curr;
    }
 
    void build(vector<int> &a, int mx_siz){
        siz = mx_siz;
        vector<int> inds;
        rep(i,sz(a)) inds.pb(i);
        root = build(a,inds,0,siz);
    }
 
    int kth(node* u, int lx, int rx, int l, int r, int k){
        if(lx == rx){
            return lx;
        }
 
        int mid = (lx+rx) >> 1;
        auto &b = u->b;
        int cnt = b[r]-b[l-1];
 
        if(k <= cnt){
            return kth(u->l,lx,mid,b[l-1]+1,b[r],k);
        }
        else{
            return kth(u->r,mid+1,rx,l-b[l-1],r-b[r],k-cnt);
        }
    }
 
    int kth(int l, int r, int k){
        return kth(root,0,siz,l+1,r+1,k);
    }
 
    pll get(node* u, int lx, int rx, int vl, int vr, int l, int r){
        if(lx > vr or rx < vl) return {0,0};
        if(!u) return {0,0};
        if(lx > rx) return {0,0};
        if(lx >= vl and rx <= vr){
            return {r-l+1,u->pref[r]-u->pref[l-1]};
        }
 
        int mid = (lx+rx) >> 1;
        auto &b = u->b;
 
        pll p1 = get(u->l,lx,mid,vl,vr,b[l-1]+1,b[r]);
        pll p2 = get(u->r,mid+1,rx,vl,vr,l-b[l-1],r-b[r]);
        return {p1.ff+p2.ff,p1.ss+p2.ss};
    }
 
    pll get(int l, int r, int k){
        return get(root,0,siz,k,siz,l+1,r+1);
    }
};

vector<int> a(N);
vector<int> b;
wavelet_tree wt;
int k;
int start;

ll get_cost(int l, int r){
    int move = min(start-l+r-l,r-start+r-l);
    if(move >= k) return 0;
    int pick = k-move;
    int len = r-l+1;
    amin(pick,len);
    int mn_pick = wt.kth(l,r,len-pick+1);
    auto [cnt,sum] = wt.get(l,r,mn_pick);
    assert(cnt >= pick);
    sum -= (cnt-pick)*b[mn_pick];
    return sum;
}

ll go(int l, int r, int optl, int optr){
    if(l > r) return 0;
    int mid = (l+r) >> 1;
    pll best = {-1,-1};

    for(int i = optl; i <= optr; ++i){
        pll px = {get_cost(mid,i),i};
        amax(best,px);
    }

    auto [ans,opt_mid] = best;
    amax(ans,go(l,mid-1,optl,opt_mid));
    amax(ans,go(mid+1,r,opt_mid,optr));

    return ans;
}

long long int findMaxAttraction(int n, int start_, int k_, int A[]) {
    start = start_;
    k = k_;
    b = vector<int>(n);
    rep(i,n) oa[i] = a[i] = b[i] = A[i];
    sort(all(b));
    b.resize(unique(all(b))-b.begin());
    rep(i,n) a[i] = lower_bound(all(b),a[i])-b.begin();
    wt.build(a,*max_element(all(a)));

    ll ans = go(0,start,start,n-1);
    return ans;
}

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