Submission #260528

#	Time	Username	Problem	Language	Result	Execution time	Memory
260528		tbzard	Holiday (IOI14_holiday)	C++14	100 / 100	814 ms	4080 KiB

holiday

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
typedef pair<pii, int> piipi;
typedef pair<pii, pii> piipii;
typedef pair<ll, ll> pll;

#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define eb emplace_back

pll ft[100005];
void update(int i, pii v){
    for(;i<=100000;i+=(i&-i)) ft[i] = mp(ft[i].fi+v.fi, ft[i].se+v.se);
}
pll query(int i){
    pll ans = mp(0, 0);
    for(;i>0;i-=(i&-i)) ans = mp(ans.fi+ft[i].fi, ans.se+ft[i].se);
    return ans;
}
int find(int k){
    int sum = 0, pos = 0;
    int i = int(log2(100000));
    while(i >= 0){
        if(pos+(1<<i) < 100001 && sum + ft[pos+(1<<i)].se < k){
            sum += ft[pos+(1<<i)].se;
            pos += (1<<i);
        }
        i--;
    }
    return pos+1;
}

int a[100005];
int L = 1, R = 0;

vector<int> sum;
void add_cost(int l, int r){
    while(L > l){
        L--;
        int idx = lower_bound(all(sum), a[L]) - sum.begin() + 1;
        update(idx, mp(-a[L], 1));
    }
    while(L < l){
        int idx = lower_bound(all(sum), a[L]) - sum.begin() + 1;
        update(idx, mp(a[L], -1));
        L++;
    }
    while(R > r){
        int idx = lower_bound(all(sum), a[R]) - sum.begin() + 1;
        update(idx, mp(a[R], -1));
        R--;
    }
    while(R < r){
        R++;
        int idx = lower_bound(all(sum), a[R]) - sum.begin() + 1;
        update(idx, mp(-a[R], 1));
    }
}

void dfs(int s, int e, int optl, int optr, int &start, int &d, ll &ans){
    if(s > e) return;
    int mid = (s+e)/2;
    int opt = -1;
    ll best = -1;
    for(int i=max(mid, optl);i<=optr;i++){
        add_cost(mid, i);
        int cost = 0;
        if(mid <= start && start <= i) cost = min(start-mid + i-mid, i-start + i-mid);
        else if(i <= start) cost = start-mid;
        else cost = i-start;
        if(cost > d) continue;

        int r = find(d-cost);
        ll res = 0;
        if(r == 100001) res += query(100000).fi;
        else{
            pll q = query(r-1);
            res += query(r-1).fi;
            int k = d-cost-q.se;
            res += k*1ll*(-sum[r-1]);
        }
        if(best < res){
            best = res;
            opt = i;
        }
        ans = max(ans, res);
    }
    if(opt == -1){
        if(mid <= start){
            dfs(mid+1, e, optl, optr, start, d, ans);
        }
        else{
            dfs(s, mid-1, optl, optr, start, d, ans);
        }
    }
    else{
        dfs(s, mid-1, optl, opt, start, d, ans);
        dfs(mid+1, e, opt, optr, start, d, ans);
    }
}
ll findMaxAttraction(int n, int start, int d, int attraction[]){
    if(d == 0) return 0;
    start++;
    for(int i=1;i<=n;i++) a[i] = -attraction[i-1];
    for(int i=1;i<=n;i++) sum.eb(a[i]);
    sort(all(sum));
    sum.erase(unique(all(sum)), sum.end());
    ll ans = 0;
    dfs(1, n, 1, n, start, d, ans);
    return ans;
}

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