Submission #97879

#	Time	Username	Problem	Language	Result	Execution time	Memory
97879		onjo0127	Holiday (IOI14_holiday)	C++11	100 / 100	802 ms	54616 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct node {
    int c;
    ll s;
    int l, r;
};

node T[2200009];

struct PST {
    int top, sz;
    vector<int> root;
    void upd(int nid, int pid, int s, int e, int x, ll y) {
        if(s == e) {
            T[nid] = {1, y, 0, 0};
            return;
        }
        int m = s+e >> 1;
        if(x <= m) {
            T[nid].l = ++top; T[nid].r = T[pid].r;
            upd(top, T[pid].l, s, m, x, y);
        }
        else {
            T[nid].l = T[pid].l; T[nid].r = ++top;
            upd(top, T[pid].r, m+1, e, x, y);
        }
        int lc = T[nid].l, rc = T[nid].r;
        T[nid].c = T[lc].c + T[rc].c;
        T[nid].s = T[lc].s + T[rc].s;
    }
    void add(int s, int e, int x, ll y) {
        int rt = ++top;
        upd(rt, root.back(), s, e, x, y);
        root.push_back(rt);
    }
    ll kth(int id1, int id2, int s, int e, int k) {
        if(s == e) return T[id2].s - T[id1].s;
        int r1 = T[id1].r, r2 = T[id2].r;
        int cr = T[r2].c - T[r1].c;
        int m = s+e >> 1;
        if(cr >= k) return kth(r1, r2, m+1, e, k);
        return kth(T[id1].l, T[id2].l, s, m, k - cr) + T[r2].s - T[r1].s;
    }
    PST(int N) {
        sz = N;
        for(int i=1; i<=4*N; i++) T[i] = {0, 0, i*2, i*2+1};
        root.push_back(1);
        top = 4*N;
    }
};

long long ans = 0;
int A[100009], B[100009], C[100009], st, dd;

void go(PST& pseg, int s, int e, int l, int r) {
    if(s > e || l > r) return;
    int m = s+e >> 1, id = l, lf;
    ll mx = -1;
    for(int i=l; i<=r; i++) {
        int lft = max(dd - (2*(st-m) + i-st), 0);
        if(lft == 0) break;
        ll v = pseg.kth(pseg.root[m-1], pseg.root[i], 1, pseg.sz, lft);
        if(mx < v) mx = v, id = i, lf = lft;
    }
    ans = max(ans, mx);
    go(pseg, s, m-1, l, id);
    go(pseg, m+1, e, id, r);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    int N = n; st = start + 1; dd = d;
    for(int i=1; i<=N; i++) A[i] = attraction[i-1];
    for(int i=1; i<=N; i++) B[i] = i;
    sort(B+1, B+N+1, [&](int P, int Q) {return A[P] < A[Q];});
    for(int i=1; i<=N; i++) C[B[i]] = i;
    for(int k=0; k<2; k++) {
        PST pseg(N);
        for(int i=1; i<=N; i++) pseg.add(1, N, C[i], A[i]);
        go(pseg, 1, st, st, N);
        reverse(A+1, A+N+1);
        reverse(C+1, C+N+1);
        st = N - st + 1;
    }
    return ans;
}

Compilation message (stderr)

holiday.cpp: In member function 'void PST::upd(int, int, int, int, int, ll)':
holiday.cpp:22:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = s+e >> 1;
                 ~^~
holiday.cpp: In member function 'll PST::kth(int, int, int, int, int)':
holiday.cpp:44:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = s+e >> 1;
                 ~^~
holiday.cpp: In function 'void go(PST&, int, int, int, int)':
holiday.cpp:61:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = s+e >> 1, id = l, lf;
             ~^~
holiday.cpp:61:31: warning: variable 'lf' set but not used [-Wunused-but-set-variable]
     int m = s+e >> 1, id = l, lf;
                               ^~
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: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53