Submission #160884

#	Time	Username	Problem	Language	Result	Execution time	Memory
160884		rama_pang	Holiday (IOI14_holiday)	C++14	100 / 100	2383 ms	7128 KiB

holiday

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

struct Treap {
    struct Node {
        lint sum; // sum of all nodes in subtree
        int val; // real value, constant
        int cnt; // size of subtree
        int prior; // random priority
        Node *l, *r;

        Node(lint v = 0): val(v), l(NULL), r(NULL), cnt(1), sum(v), prior(rand()) {}

        void update() {
            sum = val, cnt = 1;
            if (l) sum += l->sum, cnt += l->cnt;
            if (r) sum += r->sum, cnt += r->cnt;
        }

    };

    using node = Node *;

    node root;

    Treap(): root(NULL) {}

    void split(node t, node &l, node &r, int key, int add) { // implicit split, l is key-largest elements
        int cur_key = add + ((t && t->l)? t->l->cnt : 0) + 1;

        if (!t) 
            l = r = NULL;
        else if (key < cur_key) 
            split(t->l, l, t->l, key, add), r = t;
        else
            split(t->r, t->r, r, key, cur_key), l = t;

        if (t) t->update();
    }

    void split(node t, node &l, node &r, lint key) { // split based on value
        if (!t) 
            l = r = NULL;
        else if (key >= t->val) 
            split(t->l, l, t->l, key), r = t;
        else
            split(t->r, t->r, r, key), l = t;

        if (t) t->update();
    }

    void merge(node &t, node l, node r) {
        if (!l || !r) 
            t = l ? l : r;
        else if (l->prior > r->prior) 
            merge(l->r, l->r, r), t = l;
        else
            merge(r->l, l, r->l), t = r;

        if (t) t->update();
    }

    void insert(lint x) { // insert value x to the tree
        node l, r;
        split(root, l, r, x);
        merge(l, l, new Node(x));
        merge(root, l, r);
    }

    lint query(int d) { // find sum of d-largest elements in tree
        node t;
        split(root, root, t, d, 0);
        lint res = (root)? root->sum : 0;
        merge(root, root, t);

        return res;
    }

    void erase(node &t, lint x) {
        if (!t) 
            return;
        else if (t->val < x) 
            erase(t->l, x);
        else if (t->val > x)
            erase(t->r, x);
        else if (t->val == x) {
            node tmp = t;
            merge(t, t->l, t->r);
            delete tmp;
        }

        if (t) t->update();
    }

    void erase(lint x) {
        erase(root, x);
    }

    void clear(node t) {
        if (!t) return void(delete(t));
        node cur = t, l = t->l, r = t->r;
        delete cur;
        clear(l), clear(r);
    }

    void clear() {
        clear(root);
        root = NULL;
    }

};

int N, D, start;
lint ans;
Treap treap;
vector<int> endpoint; // optimal endpoints with startpoint at index
vector<int> attraction;

void solve(int start_l, int start_r, int end_l, int end_r, int cur_d, int max_d, int &ptl, int &ptr) { // iterative DFS, to allow sliding window
    if (cur_d > max_d) return;
    if (start_l > start_r) return;
    
    int start_mid = (start_l + start_r) / 2;

    if (endpoint[start_mid] != -1) {
        solve(start_l, start_mid - 1, end_l, endpoint[start_mid], cur_d + 1, max_d, ptl, ptr);
        solve(start_mid + 1, start_r, endpoint[start_mid], end_r, cur_d + 1, max_d, ptl, ptr);
        return;
    }

    lint cur_opt = -1;

    while (ptr <= start_mid && ptr < N) treap.insert(attraction[ptr++]);
    while (ptl < start_mid && ptl < N) treap.erase(attraction[ptl++]);
    
    for (lint i = end_l; i <= end_r; i++) {
        while (ptr <= i && ptr < N) treap.insert(attraction[ptr++]);
        int cnt = D - (i - start_mid) - min(start - start_mid, (int)i - start);
        lint now = treap.query(cnt);
        if (now > cur_opt) cur_opt = now, endpoint[start_mid] = i;
        ans = max(ans, now);
    }

    solve(start_l, start_mid - 1, end_l, endpoint[start_mid], cur_d + 1, max_d, ptl, ptr);
    solve(start_mid + 1, start_r, endpoint[start_mid], end_r, cur_d + 1, max_d, ptl, ptr);
}

lint findMaxAttraction(int N, int start, int D, int attraction[]) {
    srand(time(NULL));
    ::N = N, ::D = D, ::start = start;

    for (int i = 0; i < N; i++) ::attraction.push_back(attraction[i]);
    for (int i = 0; i <= start; i++) endpoint.push_back(-1);

    for (int max_d = 0; count(endpoint.begin(), endpoint.end(), -1) > 0; max_d++) {
        treap.clear();
        int ptl = 0, ptr = 0; // pointer left and right, for sliding window on iterative DFS
        solve(0, start, start, N - 1, 0, max_d, ptl, ptr);
    }

    return ans;
}

Compilation message (stderr)

holiday.cpp: In constructor 'Treap::Node::Node(lint)':
holiday.cpp:12:19: warning: 'Treap::Node::r' will be initialized after [-Wreorder]
         Node *l, *r;
                   ^
holiday.cpp:10:13: warning:   'int Treap::Node::cnt' [-Wreorder]
         int cnt; // size of subtree
             ^~~
holiday.cpp:14:9: warning:   when initialized here [-Wreorder]
         Node(lint v = 0): val(v), l(NULL), r(NULL), cnt(1), sum(v), prior(rand()) {}
         ^~~~
holiday.cpp:10:13: warning: 'Treap::Node::cnt' will be initialized after [-Wreorder]
         int cnt; // size of subtree
             ^~~
holiday.cpp:8:14: warning:   'lint Treap::Node::sum' [-Wreorder]
         lint sum; // sum of all nodes in subtree
              ^~~
holiday.cpp:14:9: warning:   when initialized here [-Wreorder]
         Node(lint v = 0): val(v), l(NULL), r(NULL), cnt(1), sum(v), prior(rand()) {}
         ^~~~

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