제출 #160855

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
160855		rama_pang	휴가 (IOI14_holiday)	C++14	47 / 100	887 ms	65540 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;
        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 print(node t) {
        if (!t) return;
        print(t->l);
        cout << t->val << " ";
        print(t->r);
    }

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

    inline 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);
    }

    inline 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();
    }

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

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

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

};

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;

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

    int ptl = 0, ptr = 0; // left pointer and right pointer
    while (!q.empty()) {
        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) {
            q.pop();
            continue;
        }
        
        if (ptl > start_mid) {
            treap.clear();
            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);
        if (start_l <= start_mid - 1) q.push({start_l, start_mid - 1, end_l, end_mid});
        if (start_mid + 1 <= start_r) q.push({start_mid + 1, start_r, end_mid, end_r});
        q.pop();
    }

    return res;
}

컴파일 시 표준 에러 (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: 0 / 53