Submission #232094

#	Time	Username	Problem	Language	Result	Execution time	Memory
232094		anonymous	Holiday (IOI14_holiday)	C++14	23 / 100	182 ms	1788 KiB

holiday

#include"holiday.h"
#include <map>
#include <vector>
#include <algorithm>
#define LL long long
#define MAXN 100005
using namespace std;
LL ans;
int A[MAXN], D, S, N;
map <int,int> Lookup;
vector <int> Sweep;
int Val[MAXN], pt;

class DS {
    LL ST[MAXN * 4][2];
    void pushup(int cur) {
        ST[cur][0] = ST[2*cur][0] + ST[2*cur+1][0];
        ST[cur][1] = ST[2*cur][1] + ST[2*cur+1][1];
    }
public:
    void nuke(int l, int r, int cur) {
        ST[cur][0] = ST[cur][1] = 0;
        if (l != r) {
            int mid = (l + r) >> 1;
            nuke(l, mid, 2*cur);
            nuke(mid+1, r, 2*cur+1);
        }
    }
    void upd(bool b, int ind, int l, int r, int cur) {
        if (ind < l || ind > r) {return;}
        if (l == r) {
            ST[cur][1] += b ? 1 : -1;
            ST[cur][0] = Val[l] * ST[cur][1];
        } else {
            int mid = (l + r) >> 1;
            upd(b, ind, l, mid, 2*cur);
            upd(b, ind, mid+1, r, 2*cur+1);
            pushup(cur);
        }
    }
    LL kth(int k, int l, int r, int cur) {
        if (l == r) {
            return(((LL) Val[l])*(min((LL) k, ST[cur][1])));
        } else {
            int mid = (l + r) >> 1;
            if (ST[2*cur+1][1] <= k) { //early exit?
                return(ST[2*cur+1][0] +
                       kth(k - ST[2*cur+1][1], l, mid, 2*cur));
            } else {
                return(kth(k, mid+1, r, 2*cur+1));
            }
        }
    }
    void add(int v) {
        upd(1, Lookup[v], 0, pt, 1);
    }
    void del(int v) {
        upd(0, Lookup[v], 0, pt, 1);
    }
    LL ask(int x) {
        if (x < 0) {return(-1LL<<60);}
        return(kth(x, 0, pt, 1));
    }

} KQ;

void Compress() {
     for (int i=0; i<N; i++) {
        Sweep.push_back(A[i]);
     }
     sort(Sweep.begin(), Sweep.end());
     for (int i=0; i<N; i++) {
        if (i == 0 || Sweep[i] != Sweep[i-1]) {
            Val[pt] = Sweep[i];
            Lookup[Sweep[i]] = pt;
            pt++;
        }
     }
}

void slv(int l, int r, int lo, int hi, int pl, int pr) {
    //printf("%d %d %d %d\n",l,r,lo,hi);
    if (l > r) {return;}
    int p = (l + r) >> 1;
    int pL = pl, pR = pr;
    while (pl > hi+1) {
        KQ.add(A[pl-1]);
        pl--;
    }
    while (pr < p) {
        KQ.add(A[pr+1]);
        pr++;
    }
    while (pl <hi+1) {
        KQ.del(A[pl]);
        pl++;
    }
    while (pr > p) {
        KQ.del(A[pr]);
        pr--;
    }

    LL opt=-1, optval=-1LL<<60;
    for (int i=hi; i>=lo; i--) {
        KQ.add(A[i]);
        LL res = KQ.ask(D-S + 2*i - p);
        if (res >= optval) {
            opt = i;
            optval = res;
            ans = max(ans, res);
        }
    }
    slv(l, p-1, lo, opt, lo, p);
    slv(p+1,r, opt, hi, lo, p);
    //reset pos
    while (lo < pL) {
        KQ.del(A[lo]);
        lo++;
    }
    while (lo > pL) {
        KQ.add(A[lo-1]);
        lo--;
    }
    while (p < pR) {
        KQ.add(A[p+1]);
        p++;
    }
    while (p > pR) {
        KQ.del(A[p]);
        p--;
    }
}

void slvL() {
    for (int i=S; i>=0; i--) { //one direction
        KQ.add(A[i]);
        ans  = max(ans, KQ.ask(D-S+i));
    }
    slv(S+1, N-1, 0, S-1, 0, S);
    KQ.nuke(0, pt, 1);
}

LL findMaxAttraction(int n, int s, int d, int a[]) { //len, start, days, val
    N = n, S = s, D = d;
    for (int i=0; i<n; i++) {A[i] = a[i];}
    Compress();
    slvL();
    for (int i=0; i<=n/2; i++) {
        swap(A[i], A[n-1-i]);
    }
    S = N - 1 - S;
    slvL();
    return(ans);
}

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