Submission #884878

#	Time	Username	Problem	Language	Result	Execution time	Memory
884878		tade	Holiday (IOI14_holiday)	C++17	100 / 100	699 ms	60752 KiB

holiday

#include <bits/stdc++.h>
using namespace std;

int log2_floor(unsigned long long i) {
    return i ? __builtin_clzll(1) - __builtin_clzll(i) : -1;
}

#define int long long
// #define ll long long
#define ld long double
#define all(x) x.begin(), x.end()

template<typename T> 
bool minimise(T &lhs, T rhs) { 
    if(lhs > rhs) { lhs = rhs; return true; }
    return false;
}
template<typename T>
bool maximise(T &lhs, T rhs) { 
    if(lhs < rhs) { lhs = rhs; return true; }
    return false;
}

const int nmax = 1e5;
const int LOG = 29;

struct trie {
    struct node {
        int sum, cnt;
        node *child[2];
        node() {
            sum = cnt = 0;
            child[0] = child[1] = NULL;
        }
    };
    node *root = new node();

    void reset() {
        // fugg the redundant memory's gonna be insane
        root = new node();
    }
    
    void add(int x) {
        node *p = root;
        ++ p->cnt;
        p->sum += x;
        for(int i = LOG; i >= 0; -- i) {
            int nxt = x >> i & 1;
            if(p->child[nxt] == NULL) p->child[nxt] = new node();
            p = p->child[nxt];
            ++ p->cnt;
            p->sum += x;
        }
    }
    bool exist(int x) {
        node *p = root;
        for(int i = LOG; i >= 0; -- i) {
            int nxt = x >> i & 1;
            if(p->child[nxt] == NULL) return false;
            p = p->child[nxt];
        }
        return true;
    }
    void del(int x) {
        if(!exist(x)) return;
        node *p = root;
        -- p->cnt;
        p->sum -= x;
        for(int i = LOG; i >= 0; -- i) {
            int nxt = x >> i & 1;
            p = p->child[nxt];
            -- p->cnt;
            p->sum -= x;
        }
    }
    
    // sum of k largest numbers
    int get(int k) {
        if(root->cnt <= k) return root->sum;
        node *p = root;
        int ans = 0, mask = 0;
        for(int i = LOG; i >= 0; -- i) {
            int j = 1;
            for(; j >= 0; -- j) {
                if(p->child[j] == NULL) continue;
                if(k > p->child[j]->cnt) {
                    k -= p->child[j]->cnt;
                    ans += p->child[j]->sum;
                }
                else break;
            }
            p = p->child[j];
            mask |= (j << i);
        }
        return ans + k * mask;
    }
} T;

int n, start, d;
int a[nmax + 5];
int f[3 * nmax + 5], optf[3 * nmax + 5], g[3 * nmax + 5], optg[3 * nmax + 5];

void dnc(int *dp, int *opt, int l, int r, int optl, int optr) {
    if(l > r || optl > optr) return;
    // cerr << l << " " << r << " " << optl << " " << optr << "\n";
    if(optl == optr) {
        for(int i = l; i <= r; ++ i) {
            opt[i] = optl;
            dp[i] = T.get(i - (optl - start));
        }
        return;
    }
    int mid = (l + r) >> 1;
    // cerr << " " << mid << "\n";
    for(int i = optr; i >= optl; -- i) {
        // cerr << "  " << i << " " << mid - (i - start) << "\n";
        int mx = T.get(mid - (i - start));
        if(mx >= dp[mid]) {
            dp[mid] = mx;
            opt[mid] = i;
        }
        // cerr << "   " << i << " " << mid - (i - start) << " " << mx << " " << opt[mid] << " " << dp[mid] << "\n";
        T.del(a[i]);
    }
    // cerr << " " << "opt done\n";
    for(int i = optl; i <= opt[mid]; ++ i) T.add(a[i]);
    dnc(dp, opt, l, mid - 1, optl, opt[mid]);
    for(int i = opt[mid] + 1; i <= optr; ++ i) T.add(a[i]);
    dnc(dp, opt, mid + 1, r, opt[mid], optr);
}

int run() {
    T.reset();
    for(int i = start; i <= n; ++ i) T.add(a[i]);
    dnc(f, optf, 1, d, start, n);

    // for(int i = 1; i <= d; ++ i) cerr << f[i] << " ";
    // cerr << "\n";
    // for(int i = 1; i <= d; ++ i) cerr << optf[i] << " ";
    // cerr << "\n";
    
    reverse(a + 1, a + 1 + n);
    start = n + 1 - start;
    T.reset();
    for(int i = start + 1; i <= n; ++ i) T.add(a[i]);
    dnc(g, optg, 1, d, start + 1, n);
    for(int i = 1; i <= d; ++ i) optg[i] = n + 1 - optg[i];

    // for(int i = 1; i <= d; ++ i) cerr << g[i] << " ";
    // cerr << "\n";
    // for(int i = 1; i <= d; ++ i) cerr << optg[i] << " ";
    // cerr << "\n";

    start = n + 1 - start;
    int ans = 0;
    for(int i = 1; i <= d; ++ i) {
        maximise(ans, max(f[i], g[i]));
        int vis_cnt = d - i - (optf[i] - start);
        if(vis_cnt >= 0) maximise(ans, f[i] + g[vis_cnt]);

        vis_cnt = d - i - (start - optg[i]);
        if(vis_cnt >= 0) maximise(ans, g[i] + f[vis_cnt]);
    }
    return ans;
}

int findMaxAttraction(int32_t _n, int32_t _start, int32_t _d, int32_t _a[]) {
    n = _n;
    start = _start + 1;
    d = _d;
    for(int i = 1; i <= n; ++ i) a[i] = _a[i - 1];
    return run();
}

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