Submission #1066125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066125		Mr_Husanboy	Holiday (IOI14_holiday)	C++17	100 / 100	437 ms	10288 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second


template<typename T>
int len(T &a){
    return a.size();
}


struct SegTree{
    vector<int> tr;
    int n;

    int join(int a, int b){
        return a + b;
    }

    int neutral(){
        return 0;
    }

    SegTree (int _n){
        n = _n;
        tr.assign(4*n, neutral());
    }

    SegTree() {}

    void init(int _n){
        n = _n;
        int sz = 1;
        while(sz < 2 * n) sz *= 2;
        tr.assign(sz, neutral());
    }

    void init(vector<int> &a){
        build(a);
    }

    void build(vector<int> &a, int x, int l, int r){
        if(l == r){
            tr[x] = a[l]; return;
        }
        int m = (l + r) >> 1;
        build(a, x * 2, l, m); build(a, x * 2 + 1, m + 1, r);
        tr[x] = join(tr[x*2], tr[x*2 + 1]);
    }

    void upd(int x, int l, int r, int &ind, int &val){
        if(l == r){
            tr[x] = val; return;
        }
        int m = (l+r) >> 1;
        if(ind <= m) upd(x * 2, l, m, ind, val);
        else upd(x * 2 + 1, m + 1, r, ind, val);

        tr[x] = join(tr[x*2], tr[x*2 + 1]);
    }

    int get(int x, int l, int r, int &kl, int &kr){
        if(l > kr || r < kl) return neutral();
        if(kl <= l && r <= kr) return tr[x];
        int m = (l + r) >> 1;
        return join(get(x * 2, l, m, kl, kr), get(x * 2 + 1, m + 1, r, kl, kr));
    }

    int findkth(int x, int l, int r, int k){
        if(k > tr[x]){
            return -1;
        }
        if(l == r){
            return l;
        }
        int tm = (l + r) >> 1;

        if(tr[x << 1] >= k){
            return findkth(x << 1, l, tm, k);
        }else{
            return findkth((x << 1) + 1, tm + 1, r, k - tr[x << 1]);
        }
    }

    // lessen

    void build(vector<int> a){
        n = a.size();
        tr.resize(4 * n);
        build(a, 1, 0, n - 1);
    }

    void upd(int ind, int val){
        upd(1, 0, n - 1, ind, val);
    }

    int get(int l, int r){
        return get(1, 0, n - 1, l, r);
    }

    int findkth(int k){
        return findkth(1, 0, n - 1, k);
    }

};

struct fenwick{
    vector<ll> t;
    int n;
    fenwick(){    }
    fenwick(int _n){
        init(_n);
    }
    void init(int _n){
        n = _n;
        t.assign(n,0);
    }
    

    void inc(int i, int val = 1){
        for(; i < n; i = i | (i + 1)){
            t[i] += val;
        }
    }
    ll get(int i){
        ll sum = 0;
        for(; i >= 0; i = (i & (i + 1)) - 1){
            sum += t[i];
        }
        return sum;
    }
    
    ll get(int l, int r){
        return get(r) - get(l - 1);
    }
};




pair<vector<ll>,vector<int>> compute(vector<ll> &a){
    int n = a.size();
    vector<ll> res(2 * n + 2);
    vector<int> opts(2 * n + 2, -1);
    vector<int> ind(n);
    iota(all(ind), 0);
    sort(all(ind), [&](int i, int j){
        return a[i] > a[j];
    });
    vector<int> ord(n);
    for(int i = 0; i < n; i ++) ord[ind[i]] = i;
    fenwick f(n);
    SegTree st(n);

    int cur = -1;

    auto make = [&](int i){
        while(cur < i){
            cur ++;
            st.upd(ord[cur], 1);
            f.inc(ord[cur], a[cur]);
        }
        while(cur > i){
            st.upd(ord[cur], 0);
            f.inc(ord[cur], -a[cur]);
            cur --;
        }
    };

    auto getkth = [&](int k){
        return f.get(st.findkth(k));
    };


    auto dc = [&](auto &dc, int l, int r, int optl, int optr)->void{
        if(l > r){
            return;
        }
        int mid = (l + r) / 2;
        int optm = -1;
        for(int i = optl; i <= min(mid - 2, optr); i ++){
            make(i);
            //cout << i << ' ' << mid << ' ' << getkth(min(i + 1, mid - (i + 1))) << endl;
            ll s = getkth(min(i + 1, mid - (i + 1)));
            if(s > res[mid]){
                res[mid] = s;
                optm = i;
            }
        }
        opts[mid] = optm;
        dc(dc, l, mid - 1, optl, optm);
        dc(dc, mid + 1, r, optm, optr);
    };
    dc(dc, 1, 2 * n + 1, 0, n - 1);
    return {res, opts};
}

long long int findMaxAttraction(int n, int start, int d, int a[]){
    if(d == 0){
        return 0;
    }
    if(d == 1 || n == 1){
        return a[start];
    }
    vector<ll> lef, rig;
    vector<int> optl, optr;
    for(int i = start - 1; i >= 0; i --){
        lef.push_back(a[i]);
    }
    for(int i = start + 1; i < n; i ++){
        rig.push_back(a[i]);
    }

    tie(rig, optr) = compute(rig);
    tie(lef, optl) = compute(lef);

    ll ans = 0;
    int m = min(d, len(rig) - 1);
    ans = max({ans, rig[m], rig[m - 1] + a[start]});
    m = min(d, len(lef) - 1);
    ans = max({ans, lef[m], lef[m - 1] + a[start]});

    for(int _ = 0; _ < 2; _ ++){
        for(int i = 1; i < min(len(lef), d); i ++){
            int rem = d - i - optl[i] - 1;
            if(rem <= 0) break;
            rem = min(rem, len(rig) - 1);
            ans = max(ans, lef[i] + rig[rem]);
            ans = max(ans, lef[i] + rig[rem - 1] + a[start]);
        }
        swap(lef, rig);
        swap(optl, optr);
    }
    
    return ans;
}

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