Submission #764215

#	Time	Username	Problem	Language	Result	Execution time	Memory
764215		boris_mihov	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	9052 ms	4316 KiB

elephants

#include "elephants.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>
#include <vector>
#include <set>

typedef long long llong;
const int MAXN = 150000 + 10;
const int INF  = 2e9;

int n, len;
int a[MAXN];
std::mt19937 mt(69);
struct Treap
{
    struct Node
    {
        struct Interval
        {
            int l, r;
            friend bool operator < (const Interval &a, const Interval &b)
            {
                return a.l < b.l;
            }
        };

        int cnt, x, y;
        Node *left, *right;
        Interval first;
        Interval last;

        Node()
        {
            left = right = nullptr;
        }

        Node (int _x, int _y)
        {
            x = _x;
            y = _y;
            cnt = 1;
            left = right = nullptr;
            first.l = first.r = x;
            last = first;
        }
    };

    Node *root;
    void recover(Node *curr)
    {
        if (curr == nullptr)
        {
            return;
        }
        
        curr->cnt = 1;
        curr->first = curr->last = {curr->x, curr->x};
    
        if (curr->left != nullptr)
        {
            if (curr->left->last.l + len >= curr->first.r)
            {
                if (curr->cnt == 1)
                {
                    curr->last = {curr->left->last.l, curr->first.r};
                }

                curr->cnt = curr->left->cnt + curr->cnt - 1;
                if (curr->left->cnt == 1)
                {
                    curr->first = {curr->left->last.l, curr->first.r};
                } else
                {
                    curr->first = curr->left->first;
                }
            } else
            {
                curr->cnt = curr->left->cnt + curr->cnt;
                curr->first = curr->left->first;
            }
        }

        if (curr->right != nullptr)
        {
            if (curr->last.l + len >= curr->right->first.r)
            {
                if (curr->cnt == 1)
                {
                    curr->first = {curr->last.l, curr->right->first.r};
                }

                curr->cnt = curr->right->cnt + curr->cnt - 1;
                if (curr->right->cnt == 1)
                {
                    curr->last = {curr->last.l, curr->right->first.r};
                } else
                {
                    curr->last = curr->right->last;
                }
            } else
            {
                curr->cnt = curr->right->cnt + curr->cnt;
                curr->last = curr->right->last;
            }
        }
    }

    void split(Node *curr, Node *&left, Node *&right, int k)
    {
        if (curr == nullptr)
        {
            left = right = nullptr;
            return;
        }

        if (curr->x <= k)
        {
            left = curr;
            split(curr->right, left->right, right, k);
            recover(left);
        } else
        {
            right = curr;
            split(curr->left, left, right->left, k);
            recover(right);
        }
    }

    void merge(Node *&curr, Node *left, Node *right)
    {
        if (left == nullptr)
        {
            curr = right;
            return;
        }

        if (right == nullptr)
        {
            curr = left;
            return;
        }

        if (left->y > right->y)
        {
            curr = left;
            merge(curr->right, left->right, right);
        } else
        {
            curr = right;
            merge(curr->left, left, right->left);
        }

        recover(curr);
    }

    void insert(int x)
    {
        Node *curr = new Node(x, mt());
        Node *left, *right;

        split(root, left, right, curr->x);
        merge(left, left, curr);
        merge(root, left, right);
    }

    void erase(int x)
    {
        Node *left, *right, *ll, *lr;

        split(root, left, right, x);
        split(left, ll, lr, x - 1);
        merge(root, ll, right);
    }

    void printTreap(Node *curr)
    {
        std::cout << curr->x << ' ' << curr->cnt << ' ' << curr->first.l << ' ' << curr->first.r << ' ' << curr->last.l << ' ' << curr->last.r << '\n';
        if (curr->left != nullptr)
        {
            std::cout << "left of: " << curr->x << '\n';
            printTreap(curr->left);
        }

        if (curr->right != nullptr)
        {
            std::cout << "right of: " << curr->x << '\n';
            printTreap(curr->right);
        }
    }

    void printTreap()
    {
        std::cout << "root\n";
        printTreap(root);
    }
};

Treap treap;
std::multiset <int> ms;
void init(int N, int L, int X[])
{
    n = N;
    len = L;
    for (int i = 0 ; i < n ; ++i)
    {
        a[i + 1] = X[i];
        treap.insert(X[i]);
        ms.insert(X[i]);
    }
}

int update(int idx, int y)
{
    a[idx + 1] = y;
    std::vector <int> vals;
    for (int i = 1 ; i <= n ; ++i)
    {
        vals.push_back(a[i]);
    } 

    int coveredTo = -1, ans = 0;
    std::sort(vals.begin(), vals.end());
    for (const int &i : vals)
    {
        if (coveredTo < i)
        {
            ans++;
            coveredTo = i + len;
        }
    }

    return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3