Submission #579089

#	Time	Username	Problem	Language	Result	Execution time	Memory
579089		tranxuanbach	Holiday (IOI14_holiday)	C++17	100 / 100	705 ms	17212 KiB

holiday

#ifndef FEXT

#include "holiday.h"

#endif

#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;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

struct segment_tree{
    pair <int, ll> seg[1 << 18];

    void build(int id, int l, int r){
        if (l == r){
            seg[id] = make_pair(0, 0);
            return;
        }
        int mid = (l + r) >> 1;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r);
        seg[id] = make_pair(0, 0);
    }

    void update(int id, int l, int r, int i, int val){
        if (l == r){
            seg[id].fi++;
            seg[id].se += val;
            return;
        }
        int mid = (l + r) >> 1;
        if (i <= mid){
            update(id * 2, l, mid, i, val);
        }
        else{
            update(id * 2 + 1, mid + 1, r, i, val);
        }
        seg[id] = make_pair(seg[id * 2].fi + seg[id * 2 + 1].fi, seg[id * 2].se + seg[id * 2 + 1].se);
    }

    ll sum_max(int id, int l, int r, int x){
        if (x >= seg[id].fi){
            return seg[id].se;
        }
        if (l == r or x <= 0){
            return 0;
        }
        int mid = (l + r) >> 1;
        if (seg[id * 2 + 1].fi > x){
            return sum_max(id * 2 + 1, mid + 1, r, x);
        }
        else{
            return sum_max(id * 2, l, mid, x - seg[id * 2 + 1].fi) + seg[id * 2 + 1].se;
        }
    }
} seg;

const int N = 1e5 + 5, M = 3e5 + 5;

#define left __left__
#define right __right__
int left[N], right[N];

pair <int, ll> ansleft[M], ansright[M];

int pos[N];

int idxopt;

void dnc(int n, int a[], pair <int, ll> ans[], int l, int r, int optl, int optr, queue <tuple <int, int, int, int>> &qu){
    int mid = (l + r) >> 1;
    ans[mid] = make_pair(-1, 0);

    if (optl < idxopt){
        seg.build(1, 0, n - 1);
        idxopt = 0;
        seg.update(1, 0, n - 1, pos[idxopt], a[idxopt]);
    }
    ForE(opt, optl, optr){
        while (idxopt < opt){
            idxopt++;
            seg.update(1, 0, n - 1, pos[idxopt], a[idxopt]);
        }
        ll val = seg.sum_max(1, 0, n - 1, mid - opt);
        if (ans[mid].fi == -1 or ans[mid].se < val){
            ans[mid] = make_pair(opt, val);
        }
    }

    // if (mid < 10){
    //     cout << "dnc " << l << ' ' << r << ' ' << mid << ' ' << ans[mid].fi << ' ' << ans[mid].se << endl;
    // }

    if (l < mid){
        qu.emplace(l, mid - 1, optl, ans[mid].fi);
    }
    if (mid < r){
        qu.emplace(mid + 1, r, ans[mid].fi, optr);
    }
}

void findMaxAttractionStart1(int n, int a[], pair <int, ll> ans[]){
    // cout << "findMaxAttractionStart1 " << n << endl;
    // For(i, 0, n){
    //     cout << a[i] << ' ';
    // } cout << endl;
    {
        vpii b;
        For(i, 0, n){
            b.emplace_back(a[i], i);
        }
        sort(bend(b));
        For(i, 0, n){
            pos[b[i].se] = i;
        }
    }

    idxopt = n;

    queue <tuple <int, int, int, int>> qu;
    qu.emplace(0, 2 * n, 0, n - 1);

    while (!qu.empty()){
        int l, r, optl, optr; tie(l, r, optl, optr) = qu.front(); qu.pop();
        dnc(n, a, ans, l, r, optl, optr, qu);
    }

    For(i, 2 * n + 1, M){
        ans[i] = ans[i - 1];
    }

    // For(i, 0, 10){
    //     cout << i << ' ' << ans[i].fi << ' ' << ans[i].se << endl;
    // }
}

ll findMaxAttraction(int n, int start, int d, int a[]){
    ll ans = 0;

    FordE(i, start, 0){
        left[start - i] = a[i];
    }
    findMaxAttractionStart1(start + 1, left, ansleft);
    ForE(dl, 0, d){
        ans = max(ans, ansleft[dl].se);
    }
    if (start < n - 1){
        For(i, start + 1, n){
            right[i - start - 1] = a[i];
        }
        findMaxAttractionStart1(n - start - 1, right, ansright);
        ForE(dl, 0, d){
            int dr = d - dl - ansleft[dl].fi - 1;
            if (!(0 <= dr and dr <= d)){
                continue;
            }
            // cout << "dl dr left " << dl << ' ' << dr << endl;
            // cout << ansleft[dl].fi << ' ' << ansleft[dl].se << ' ' << ansright[dr].fi << ' ' << ansright[dr].se << endl;
            ans = max(ans, ansleft[dl].se + ansright[dr].se);
        }
    }

    For(i, start, n){
        right[i - start] = a[i];
    }
    findMaxAttractionStart1(n - start, right, ansright);
    ForE(dr, 0, d){
        ans = max(ans, ansright[dr].se);
    }
    if (start > 0){
        FordE(i, start - 1, 0){
            left[start - 1 - i] = a[i];
        }
        findMaxAttractionStart1(start, left, ansleft);
        ForE(dr, 0, d){
            int dl = d - dr - ansright[dr].fi - 1;
            if (!(0 <= dl and dl <= d)){
                continue;
            }
            // cout << "dl dr right " << dl << ' ' << dr << endl;
            // cout << ansleft[dl].fi << ' ' << ansleft[dl].se << ' ' << ansright[dr].fi << ' ' << ansright[dr].se << endl;
            ans = max(ans, ansleft[dl].se + ansright[dr].se);
        }
    }
    return ans;
}

#ifdef FEXT

int a[100005];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    freopen("KEK.inp", "r", stdin);
    freopen("KEK.out", "w", stdout);
    int n, start, d; cin >> n >> start >> d;
    For(i, 0, n){
        cin >> a[i];
    }

    ll ans = findMaxAttraction(n, start, d, a);
    cout << ans << endl;
}

#endif

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

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