Submission #30952

#	Time	Username	Problem	Language	Result	Execution time	Memory
30952		kajebiii	Holiday (IOI14_holiday)	C++14	24 / 100	79 ms	65536 KiB

holiday

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

struct NODE{
    int l, r;
    ll sum; int cnt;
    NODE *lp, *rp;
    NODE() : l(0), r(0), sum(0ll), cnt(0), lp(NULL), rp(NULL) {}
    NODE(int a, int b) : l(a), r(b), sum(0ll), cnt(0), lp(NULL), rp(NULL) {
        if(a == b) return;
        int m = (a+b) >> 1;
        lp = new NODE(a, m);
        rp = new NODE(m+1, b);
    }
    NODE *add(int v, int k, int nr[]) {
        if(r < v || v < l) return this;
        NODE *res = new NODE(); res->l = l; res->r = r;
        if(l != r) {
            res->lp = lp->add(v, k, nr);
            res->rp = rp->add(v, k, nr);
        }
        res->cnt = cnt + k;
        res->sum = sum + nr[v] * k;
        return res;
    }
    ll getMaxSum(int k) {
        if(k <= 0) return 0ll;
        if(l == r) return sum;
        if(rp->cnt >= k) return rp->getMaxSum(k);
        return lp->getMaxSum(k - rp->cnt) + rp->sum;
    }
    ~NODE() {
        if(lp != NULL) delete lp;
        if(rp != NULL) delete rp;
    }
};
NODE *root[MAX_N];

int N, St, D, Att[MAX_N];
int sortIx[MAX_N], sortV[MAX_N];
ll Dy[2][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 = root[x]->getMaxSum(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_;
    for(int i=0; i<N; i++) Att[i] = att_[i];
    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] = NULL;
    root[St] = new NODE(0, N-1);
    for(int d=0; d<2; d++) {
        int dir = d*2 - 1;
//        for(int i=0; i<N; i++) if(root[i] != NULL) delete root[i];
//        root[St] = root[St]->add(sortIx[St], 1, sortV);
        for(int i=St+dir; i>=0 && i<N; i+=dir)
            root[i] = root[i-dir]->add(sortIx[i], 1, sortV);
        for(int w=0; w<2; w++) {
            calc(dir, w+1, 0, D, 0, N, Dy[d][w]);
//            printf("dir %d | wei %d\n", dir, w+1); for(int i=0; i<=D; i++) printf("%lld ", Dy[d][w][i]); puts("");
//            return 0;
        }
    }
    ll ans = -LINF;
    for(int d=0; d<=D; d++) {
        ans = max(ans, Dy[0][0][d] + Dy[1][1][D-d]);
        ans = max(ans, Dy[1][0][d] + Dy[0][1][D-d]);
        if(d) {
            ans = max(ans, Att[St] + Dy[0][0][d-1] + Dy[1][1][D-d]);
            ans = max(ans, Att[St] + Dy[1][0][d-1] + Dy[0][1][D-d]);
        }
    }
    return ans;
}

Compilation message (stderr)

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 / 7
• Subtask 2: 0 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53