Submission #160844

#	Time	Username	Problem	Language	Result	Execution time	Memory
160844		rama_pang	Holiday (IOI14_holiday)	C++14	47 / 100	835 ms	65536 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
        lint val; // real value, constant
        int cnt; // size of subtree
        int prior; // priority
        Node *l, *r;

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

        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 print(node t) {
        if (!t) return;
        print(t->l);
        cout << t->val << " ";
        print(t->r);
    }

    void print() {
        cout << "Treap is ";
        print(root);
        cout << "\n";
    }

    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 t1, t2;
        split(root, t1, t2, d, 0);
        lint res = (t1)? t1->sum : 0;
        merge(root, t1, t2);

        return res;
    }

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

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

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

    void clear() {
        clear(root);
    }

};

struct Query {
    int sl, sr; // startpoints to be computed
    int el, er; // possible endpoints to be computed
};

lint findMaxAttraction(int N, int start, int D, int attraction[]) {
    Treap treap;
    lint res = 0;

    deque<Query> q;
    q.push_back({0, start, start, N - 1});

    int ptl = 0, ptr = 0; // left pointer and right pointer
    for (int ptl = 0, ptr = 0; !q.empty(); q.pop_front()) {
        int start_l = q.front().sl, start_r = q.front().sr;
        int end_l = q.front().el, end_r = q.front().er;

        int start_mid = (start_l + start_r) / 2;
        int end_mid = -1;

        if (start_l > start_r) continue;
        if (ptl > start_mid) {
            treap.clear();
            q.push_front({start_l, start_r, end_l, end_r});
            ptl = ptr = 0;
            continue;
        }

        while (ptr <= start_mid && ptr < N) treap.insert(attraction[ptr++]);
        while (ptl < start_mid && ptl < N) treap.erase(attraction[ptl++]);

        lint cur_opt = -1;
        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, end_mid = i;
        }

        res = max(res, cur_opt);
        q.push_back({start_l, start_mid - 1, end_l, end_mid});
        q.push_back({start_mid + 1, start_r, end_mid, end_r});
    }

    return res;
}

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), prior(rand()), l(NULL), r(NULL), cnt(1), sum(v) {}
         ^~~~
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), prior(rand()), l(NULL), r(NULL), cnt(1), sum(v) {}
         ^~~~
holiday.cpp: In function 'lint findMaxAttraction(int, int, int, int*)':
holiday.cpp:135:9: warning: unused variable 'ptl' [-Wunused-variable]
     int ptl = 0, ptr = 0; // left pointer and right pointer
         ^~~
holiday.cpp:135:18: warning: unused variable 'ptr' [-Wunused-variable]
     int ptl = 0, ptr = 0; // left pointer and right pointer
                  ^~~

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