oj.uz

Submission #30959

# Submission time Handle Problem Language Result Execution time Memory
30959 2017-08-02T03:47:12 Z kajebiii Holiday (IOI14_holiday) C++14
100 / 100
 956 ms 60768 KB 
#include "holiday.h"
#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<double, double> pd;
typedef pair<int, int> pi; 
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;

const int MAX_N = 1e5 + 100, MAX_D = MAX_N * 2.6;

ll test = 0;
struct NODE{
    ll sum; int cnt;
    int lp, rp;
    NODE() : sum(0ll), cnt(0), lp(-1), rp(-1) {}
    NODE(ll s, int c, int l, int r) : sum(s), cnt(c), lp(l), rp(r) {}
};
NODE nd[MAX_N * 22]; int all;

int init(int a, int b) {
    ll sum = 0ll; int cnt = 0, lp = -1, rp = -1;
    if(a != b) {
        int m = (a+b) >> 1;
        lp = init(a, m);
        rp = init(m+1, b);
    }
    nd[++all] = NODE(sum, cnt, lp, rp);
    return all;
}
int add(int now, int l, int r, int v, int k, int nr[]) {
    int m = (l+r) >> 1;
    if(r < v || v < l) return now;
    int lp = -1, rp = -1;
    test++;
    if(l != r) {
        lp = add(nd[now].lp, l, m, v, k, nr);
        rp = add(nd[now].rp, m+1, r, v, k, nr);
    }
    int cnt = nd[now].cnt + k;
    ll sum = nd[now].sum + nr[v] * k;
    nd[++all] = NODE(sum, cnt, lp, rp);
    return all;
}
ll getMaxSum(int now, int l, int r, int k) {
    int lp = nd[now].lp, rp = nd[now].rp; ll sum = nd[now].sum;
    int m = (l+r) >> 1;
    if(k <= 0) return 0ll;
    if(l == r) return sum;
    if(nd[rp].cnt >= k) return getMaxSum(rp, m+1, r, k);
    return getMaxSum(lp, l, m, k - nd[rp].cnt) + nd[rp].sum;
}
int root[MAX_N];

int N, St, D, sortIx[MAX_N], sortV[MAX_N];
ll Dy[2][MAX_D];
void calc(int dir, int wei, int s, int e, int p, int q, ll dy[]) {
    if(s > e) return;
//    printf("%d %d %d %d\n", s, e, p, q);
    int m = (s+e) >> 1, k = -1;
    dy[m] = -LINF;
    for(int l=p, x=St+l*dir; l<=q && x>=0 && x<N; l++, x+=dir) {
        int rest = m - l*wei;
        if(rest < 0) continue;
        ll val = getMaxSum(root[x], 0, N-1, rest);
//        printf("in %d -> getMaxSum(%d) = %lld\n", x, rest, val);
        if(dy[m] < val) dy[m] = val, k = l;
    }
    calc(dir, wei, s, m-1, p, k, dy);
    calc(dir, wei, m+1, e, k, q, dy);
}
ll findMaxAttraction(int n_, int st_, int d_, int att_[]) {
    N = n_; St = st_; D = d_;
    vector<pi> v_ix;
    for(int i=0; i<N; i++) v_ix.push_back(pi(att_[i], i));
    sort(ALL(v_ix));
    for(int i=0; i<N; i++) {
        sortV[i] = v_ix[i].one;
        sortIx[v_ix[i].two] = i;
    }

    for(int i=0; i<N; i++) root[i] = -1;
    root[St] = init(0, N-1);
    for(int d=0; d<2; d++) {
        int dir = d*2 - 1;
        for(int i=St+dir; i>=0 && i<N; i+=dir)
            root[i] = add(root[i-dir], 0, N-1, sortIx[i], 1, sortV);
    }
    ll ans = -LINF;
    calc(-1, 1, 0, D, 0, N, Dy[0]);
    calc(+1, 2, 0, D, 0, N, Dy[1]);
    for(int d=0; d<=D; d++) {
        ans = max(ans, Dy[0][d] + Dy[1][D-d]);
        if(d) {
            ans = max(ans, att_[St] + Dy[0][d-1] + Dy[1][D-d]);
        }
    }
    calc(+1, 1, 0, D, 0, N, Dy[0]);
    calc(-1, 2, 0, D, 0, N, Dy[1]);
    for(int d=0; d<=D; d++) {
        ans = max(ans, Dy[0][d] + Dy[1][D-d]);
        if(d) {
            ans = max(ans, att_[St] + Dy[0][d-1] + Dy[1][D-d]);
        }
    }
    return ans;
}

Compilation message

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 789 ms 60760 KB Output is correct
2 Correct 943 ms 60764 KB Output is correct
3 Correct 833 ms 60760 KB Output is correct
4 Correct 956 ms 60760 KB Output is correct
5 Correct 806 ms 60764 KB Output is correct
6 Correct 263 ms 59608 KB Output is correct
7 Correct 426 ms 60000 KB Output is correct
8 Correct 519 ms 59996 KB Output is correct
9 Correct 223 ms 59608 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 59280 KB Output is correct
2 Correct 16 ms 59284 KB Output is correct
3 Correct 16 ms 59284 KB Output is correct
4 Correct 19 ms 59288 KB Output is correct
5 Correct 13 ms 59284 KB Output is correct
6 Correct 3 ms 59140 KB Output is correct
7 Correct 0 ms 59144 KB Output is correct
8 Correct 13 ms 59148 KB Output is correct
9 Correct 6 ms 59144 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 599 ms 60764 KB Output is correct
2 Correct 809 ms 60764 KB Output is correct
3 Correct 136 ms 59996 KB Output is correct
4 Correct 26 ms 59280 KB Output is correct
5 Correct 23 ms 59140 KB Output is correct
6 Correct 6 ms 59144 KB Output is correct
7 Correct 13 ms 59144 KB Output is correct
8 Correct 773 ms 60760 KB Output is correct
9 Correct 699 ms 60768 KB Output is correct