oj.uz

답안 #764198

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
764198 2023-06-23T08:32:32 Z boris_mihov 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
10 / 100
 1 ms 340 KB 
#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->first.l + len >= curr->last.r)
            {
                if (curr->cnt == 1)
                {
                    curr->last = {curr->left->first.l, curr->last.r};
                }

                curr->cnt = curr->left->cnt + curr->cnt - 1;
                if (curr->left->cnt == 1)
                {
                    curr->first = {curr->left->first.l, curr->last.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->last.r};
                }

                curr->cnt = curr->right->cnt + curr->cnt - 1;
                if (curr->right->cnt == 1)
                {
                    curr->last = {curr->last.l, curr->right->last.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)
{
    idx++;
    ms.erase(ms.find(a[idx]));
    if (!ms.count(a[idx]))
    {
        treap.erase(a[idx]);
    }

    a[idx] = y;
    if (!ms.count(a[idx]))
    {
        treap.insert(a[idx]);
    }

    ms.insert(a[idx]);
    return treap.root->cnt;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -