제출 #645095

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
645095		boris_mihov	푸드 코트 (JOI21_foodcourt)	C++17	0 / 100	341 ms	524288 KiB

foodcourt

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 250000 + 10;
const int INF  = 1e9;

struct Node
{
    Node *left, *right;
    int color, quantity;
    int subtreeSize;
    int y;

    Node()
    {
        left = right = nullptr;
        subtreeSize = 0;
    }

    Node(int _color, int _quantity)
    {
        y = rand();
        color = _color;
        quantity = _quantity;
        subtreeSize = quantity;
        left = right = nullptr;
    }
};

inline void recover(Node *curr)
{
    if (curr == nullptr) return;
    
    curr->subtreeSize = curr->quantity;
    if (curr->left != nullptr) curr->subtreeSize += curr->left->subtreeSize;
    if (curr->right != nullptr) curr->subtreeSize += curr->right->subtreeSize;
}

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

    int s = curr->quantity;
    if (curr->left != nullptr) s += curr->left->subtreeSize;
    if (k >= s)
    {
        left = curr;
        split(curr->right, left->right, right, k - s);
        recover(left);
    } else
    {
        right = curr;
        split(curr->left, left, right->left, k);
        if (curr->left == nullptr)
        {
            right->quantity -= 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);
}

int findKth(Node *curr, int k)
{
    if (curr == nullptr) return 0;
    if (curr->subtreeSize < k) return 0;

    int s = 0;
    if (curr->left != nullptr) s += curr->left->quantity;
    if (k > s && k <= s + curr->quantity) return curr->color;
    if (k < s) return findKth(curr->left, k);
    return findKth(curr->right, k - s - curr->quantity);
}

inline void push(Node *&curr, int color, int quantity)
{
    Node *newNode = new Node(color, quantity);
    merge(curr, curr, newNode);
}

inline void pop(Node *&curr, int quantity)
{
    Node *left, *right;
    split(curr, left, right, quantity);
    curr = right;
}

Node *queues[MAXN];
struct SegmentNode
{
    Node *lazy;
    int popLazy;
    SegmentNode()
    {
        lazy = nullptr;
        popLazy = 0;
    }

} tree[4*MAXN];

void pushLazy(int node, int l, int r)
{
    if (tree[node].lazy == nullptr && tree[node].popLazy == 0) return;
    if (l == r)
    {
        merge(queues[l], queues[l], tree[node].lazy);
        pop(queues[l], tree[node].popLazy);
        tree[node].lazy = nullptr;
        tree[node].popLazy = 0;
    } else
    {
        tree[2*node].popLazy += tree[node].popLazy;
        tree[2*node + 1].popLazy += tree[node].popLazy;
        merge(tree[2*node].lazy, tree[2*node].lazy, tree[node].lazy);
        merge(tree[2*node + 1].lazy, tree[2*node + 1].lazy, tree[node].lazy);
        tree[node].lazy = nullptr;
        tree[node].popLazy = 0;
    }
}

void updatePush(int l, int r, int node, int queryL, int queryR, int color, int quantity)
{
    pushLazy(node, l, r);
    if (queryR <  l || r  < queryL) return;
    if (queryL <= l && r <= queryR)
    {
        push(tree[node].lazy, color, quantity);
        pushLazy(node, l, r);
        return;
    }

    int mid = (l + r) / 2;
    updatePush(l, mid, 2*node, queryL, queryR, color, quantity);
    updatePush(mid + 1, r, 2*node + 1, queryL, queryR, color, quantity);
}

void updatePop(int l, int r, int node, int queryL, int queryR, int quantity)
{
    pushLazy(node, l, r);
    if (queryR <  l || r  < queryL) return;
    if (queryL <= l && r <= queryR)
    {
        tree[node].popLazy += quantity;
        pushLazy(node, l, r);
        return;
    }

    int mid = (l + r) / 2;
    updatePop(l, mid, 2*node, queryL, queryR, quantity);
    updatePop(mid + 1, r, 2*node + 1, queryL, queryR, quantity);
}

int query(int l, int r, int node, int queryPos, int queryVal)
{
    pushLazy(node, l, r);
    if (l == r)
    {
        return findKth(queues[l], queryVal);
    }

    int mid = (l + r) / 2;
    if (queryPos <= mid) return query(l, mid, 2*node, queryPos, queryVal);
    return query(mid + 1, r, 2*node + 1, queryPos, queryVal); 
}

int n, m, q;
int main()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);

    int qType, l, r, c, k;
    std::cin >> n >> m >> q;
    for (int i = 1 ; i <= q ; ++i)
    {
        std::cin >> qType;
        if (qType == 1)
        {
            std::cin >> l >> r >> c >> k;
            updatePush(1, n, 1, l, r, c, k);
            continue;
        }

        if (qType == 2)
        {
            std::cin >> l >> r >> k;
            updatePop(1, n, 1, l, r, k);
            continue;
        }

        if (qType == 3)
        {
            std::cin >> l >> k;
            std::cout << query(1, n, 1, l, k) << '\n';
            continue;
        }
    }

    return 0;
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 21
• Subtask 5: 0 / 15
• Subtask 6: 0 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11