Submission #1036868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036868		dwuy	Holiday (IOI14_holiday)	C++14	100 / 100	201 ms	6388 KiB

holiday

/**         - dwuy -

　　　　　 ／＞　   フ
　　　　　 | 　_　 _|
　 　　　 ／`ミ _x ノ
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

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

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) (int)((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "test"
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 100005;

int n, p, k;
int a[MX];

namespace Cost{
    struct BIT{
        int n;
        vector<int> cnt, sum;

        BIT(int n=0){
            this->n = n;
            this->cnt.assign(n + 5, 0);
            this->sum.assign(n + 5, 0);
        }

        void update(int idx, int val, int f){
            for(; idx<=n; idx+=-idx&idx){
                cnt[idx] += f;
                sum[idx] += val*f;
            }
        }

        int get(int k){
            int res = 0;
            int pos = 0;
            for(int mask=MASK(__lg(n)); mask; mask>>=1){
                if((pos|mask) <= n && cnt[pos|mask] <= k){
                    pos |= mask;
                    k -= cnt[pos];
                    res += sum[pos];
                }
            }
            return -res;
        }
    } bit(MX);

    int n, k, pos;
    int l, r;
    int a[MX];
    int b[MX];
    vector<pii> rv;

    void build(int32_t N, int32_t K, int32_t POS, int32_t *attraction){
        n = N;
        k = K;
        pos = POS;
        rv.resize(n);
        for(int i=1; i<=n; i++){
            a[i] = -attraction[i - 1];
            rv[i - 1] = {a[i], i};
        }
        sort(rv.begin(), rv.end());
        for(int i=1; i<=n; i++){
            b[i] = lower_bound(rv.begin(), rv.end(), pii(a[i], i)) - rv.begin() + 1;
        } 
        l = r = 1;
        bit.update(b[1], a[1], 1);
    }

    int calc(int u, int v){
        int dis = v - u + min(abs(u - pos), abs(v - pos));
        if(dis >= k) return 0;
        while(r < v){
            r++;
            bit.update(b[r], a[r], 1);
        }
        while(l > u){
            l--;
            bit.update(b[l], a[l], 1);
        }
        while(r > v){
            bit.update(b[r], a[r], -1);
            r--;
        }
        while(l < u){
            bit.update(b[l], a[l], -1);
            l++;
        }
        return bit.get(k - dis);
    }
};

int dwuy(int l, int r, int fx, int fy){
    if(l > r) return 0;
    int mid = (l + r)>>1;
    pii best = {-1e18, 0};
    for(int i=fx; i<=fy; i++){
        best = max(best, {Cost::calc(i, mid), i});
    }
    return max({best.fi, dwuy(l, mid - 1, fx, best.se), dwuy(mid + 1, r, best.se, fy)});
}

int findMaxAttraction(int32_t N, int32_t START, int32_t D, int32_t ATTRACTION[]) {
    Cost::build(N, D, START + 1, ATTRACTION);
    return dwuy(START + 1, N, 1, START + 1);
}

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