Submission #802986

#	Time	Username	Problem	Language	Result	Execution time	Memory
802986		thimote75	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	0 / 100	7 ms	2036 KiB

worst_reporter2

#include <bits/stdc++.h>
#define int long long

using namespace std;
using Point = pair<int, int>;
using idata = vector<int>;

struct Node {
    int pos, delta, rng;

    int ssize = 1;
    int sdelt = 0;

    Node* left; Node* right;
    void compute () {
        ssize = 1;
        sdelt = delta;

        if (left != nullptr) {
            ssize += left->ssize;
            sdelt += left->sdelt;
        }
        if (right != nullptr) {
            ssize += right->ssize;
            sdelt += right->sdelt;
        }
    }
};

struct Treap {
    Node* root;
    static void __show (Node* node, int depth) {
        if (node == nullptr) {
            for (int i = 0; i < depth; i ++) cout << " ";
            cout << ">\n";
            return ;
        }

        for (int i = 0; i < depth; i ++) cout << " ";
        cout << "> " << node->pos << " " << node->delta << endl;

        __show(node->left, depth + 1);
        __show(node->right, depth + 1);
    }
    void show () {
        __show(root, 0);
    }

    static Node* __merge (Node* A, Node* B) {
        if (A == nullptr) return B;
        if (B == nullptr) return A;

        if (A->rng >= B->rng) {
            A->right = __merge(A->right, B);
            A->compute();
            return A;
        } else {
            B->left = __merge(A, B->left);
            B->compute();
            return B;
        }
    }
    static pair<Node*, Node*> __split (Node* A, int k) {
        if (A == nullptr) return { nullptr, nullptr };

        if (A->pos > k) {
            const auto [LL, LR] = __split(A->left, k);
            
            A->left = LR;
            A->compute();
            return { LL, A };
        } else {
            const auto [RL, RR] = __split(A->right, k);

            A->right = RL;
            A->compute();
            return { A, RR };
        }
    }

    void insert( int pos, int delta ) {
        Node* node = new Node();

        node->pos = pos;
        node->delta = delta;
        node->rng = rand();
        node->sdelt = delta;

        const auto ldata = __split(root, pos - 1);
        Node* left  = ldata.first;
        const auto rdata = __split(ldata.second, pos);
        Node* right = rdata.second;
        Node* mid   = rdata.first;

        if (mid == nullptr) mid = node;
        else {
            delete node;
            mid->delta += delta;
            mid->sdelt += delta;
        }

        root = __merge(left, __merge(mid, right));
    }
    int query (int x) {
        Node* local = root;

        int res = 0;
        while (local != nullptr) {
            if (local->pos > x) local = local->left;
            else {
                res += local->delta;
                if (local->left != nullptr) res += local->left->sdelt;
            
                local = local->right;
            }
        }

        return res;
    }
    void __chmin (Node* node, int until) {
        if (node == nullptr) return ;

        if (node->left != nullptr) {
            if (node->left->sdelt > until) {
                __chmin(node->left, until);
                node->right = nullptr;
                node->delta = 0;
                node->compute();
                return ;
            } else until -= node->left->sdelt;
        }

        if (until < node->delta) {
            node->delta = until;
            node->right = nullptr;
            node->compute();
            return ;
        }
        until -= node->delta;

        __chmin(node->right, until);
    }
    void chmin (int until) {
        __chmin(root, until);
    }

    Treap cut (int position) {
        const auto data = __split(root, position);

        root = data.first;

        Treap other; other.root = data.second;
        return other;
    }

    static void __traverse (Node* node, vector<Node*> &answer) {
        if (node == nullptr) return ;
        answer.push_back(node);

        __traverse(node->left,  answer);
        __traverse(node->right, answer);
    }
    vector<Node*> traverse () {
        vector<Node*> ans;
        __traverse(root, ans);

        return ans;
    }

    int size () { return root != nullptr ? root->ssize : 0; }
    void swap (Treap &other) {
        Node* c = root;
        root = other.root;
        other.root = c;
    }
};

void compile (Treap &treap, int H_i, int C_i) {
    int chmin_left = treap.query( H_i );
    Treap right = treap.cut(H_i);

    right.insert( H_i + 1, C_i );

    treap.insert( - 1e9, C_i );
    treap.chmin( chmin_left );
    
    treap.root = treap.__merge(treap.root, right.root);
}

void merge (Treap &target, Treap &other) {
    if (target.size() < other.size())
        target.swap(other);
    
    for (Node* node : other.traverse())
        target.insert(node->pos, node->delta);
}

vector<Treap> treapArray;

idata A, H, C;

signed main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    treapArray.resize(N);

    A.resize(N); H.resize(N); C.resize(N);
    for (int i = 0; i < N; i ++) {
        cin >> A[i] >> H[i] >> C[i];
        A[i] --;

        if ((i != 0 && A[i] > i - 1) || (i == 0 && A[i] != 0)) return 0;
    }
    
    for (int i = N - 1; i >= 0; i --) {
        compile(treapArray[i], H[i], C[i]);

        if (i == 0) continue ;
        merge(treapArray[A[i]], treapArray[i]);
    }

    cout << treapArray[0].query(1) << endl;
}

Compilation message (stderr)

worst_reporter2.cpp: In static member function 'static std::pair<Node*, Node*> Treap::__split(Node*, long long int)':
worst_reporter2.cpp:68:24: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |             const auto [LL, LR] = __split(A->left, k);
      |                        ^
worst_reporter2.cpp:74:24: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |             const auto [RL, RR] = __split(A->right, k);
      |                        ^

• Subtask 1: 0 / 14
• Subtask 2: 0 / 65
• Subtask 3: 0 / 21