oj.uz

Submission #260528

# Submission time Handle Problem Language Result Execution time Memory
260528 2020-08-10T13:07:32 Z tbzard Holiday (IOI14_holiday) C++14
100 / 100
 814 ms 4080 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 1916 KB Output is correct
2 Correct 214 ms 1916 KB Output is correct
3 Correct 262 ms 1916 KB Output is correct
4 Correct 208 ms 1916 KB Output is correct
5 Correct 339 ms 1916 KB Output is correct
6 Correct 94 ms 904 KB Output is correct
7 Correct 179 ms 1280 KB Output is correct
8 Correct 224 ms 1408 KB Output is correct
9 Correct 66 ms 768 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 512 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 8 ms 512 KB Output is correct
4 Correct 11 ms 512 KB Output is correct
5 Correct 10 ms 512 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 2684 KB Output is correct
2 Correct 362 ms 4080 KB Output is correct
3 Correct 178 ms 2044 KB Output is correct
4 Correct 10 ms 512 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 812 ms 3832 KB Output is correct
9 Correct 814 ms 3824 KB Output is correct