Submission #1307210

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307210		micodiy	Matryoshka (JOI16_matryoshka)	C++20	0 / 100	1 ms	580 KiB

matryoshka

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200000;
const int MAXQ = 200000;
const int MAXV = 400000; // N + Q

struct Doll {
    int R, H;
};

struct Query {
    int A, B, id;
};

struct Node {
    int val;
    Node *left, *right;
    Node() : val(0), left(nullptr), right(nullptr) {}
    Node(int v, Node* l, Node* r) : val(v), left(l), right(r) {}
};

int N, Q;
Doll dolls[MAXN];
Query queries[MAXQ];
vector<int> values;
int compH[MAXN];
int compB[MAXQ];
int ans[MAXQ];

Node* roots[MAXN + 1];
Node* nullNode;

Node* build(int l, int r) {
    if (l == r) return new Node(0, nullNode, nullNode);
    int mid = (l + r) >> 1;
    return new Node(0, build(l, mid), build(mid + 1, r));
}

Node* update(Node* node, int l, int r, int pos, int val) {
    if (l == r) return new Node(val, nullNode, nullNode);
    int mid = (l + r) >> 1;
    if (pos <= mid) {
        Node* newLeft = update(node->left, l, mid, pos, val);
        return new Node(max(newLeft->val, node->right->val), newLeft, node->right);
    } else {
        Node* newRight = update(node->right, mid + 1, r, pos, val);
        return new Node(max(node->left->val, newRight->val), node->left, newRight);
    }
}

int query(Node* node, int l, int r, int L, int R) {
    if (node == nullNode || r < L || R < l) return 0;
    if (L <= l && r <= R) return node->val;
    int mid = (l + r) >> 1;
    return max(query(node->left, l, mid, L, R),
               query(node->right, mid + 1, r, L, R));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    nullNode = new Node(0, nullptr, nullptr);
    nullNode->left = nullNode->right = nullNode;

    cin >> N >> Q;
    for (int i = 0; i < N; ++i) {
        cin >> dolls[i].R >> dolls[i].H;
        values.push_back(dolls[i].H);
    }
    for (int i = 0; i < Q; ++i) {
        cin >> queries[i].A >> queries[i].B;
        queries[i].id = i;
        values.push_back(queries[i].B);
    }

    // Сжатие координат высот
    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());
    int M = values.size();

    for (int i = 0; i < N; ++i) {
        compH[i] = lower_bound(values.begin(), values.end(), dolls[i].H) - values.begin() + 1;
    }
    for (int i = 0; i < Q; ++i) {
        compB[i] = lower_bound(values.begin(), values.end(), queries[i].B) - values.begin() + 1;
    }

    // Сортировка матрёшек по убыванию R
    vector<int> order(N);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
        if (dolls[i].R != dolls[j].R) return dolls[i].R > dolls[j].R;
        return dolls[i].H > dolls[j].H;
    });

    // Построение персистентного дерева отрезков
    roots[0] = build(1, M);
    for (int i = 0; i < N; ++i) {
        int idx = order[i];
        int h = compH[idx];
        int cur = query(roots[i], 1, M, 1, h) + 1;
        roots[i + 1] = update(roots[i], 1, M, h, cur);
    }

    // Обработка запросов
    for (int i = 0; i < Q; ++i) {
        int A = queries[i].A;
        int B = compB[i];

        // Бинарный поиск последней матрёшки с R >= A
        int lo = 0, hi = N - 1, idx = -1;
        while (lo <= hi) {
            int mid = (lo + hi) >> 1;
            if (dolls[order[mid]].R >= A) {
                idx = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        if (idx == -1) {
            ans[queries[i].id] = 0;
        } else {
            Node* root = roots[idx + 1];
            ans[queries[i].id] = query(root, 1, M, 1, B);
        }
    }

    for (int i = 0; i < Q; ++i) {
        cout << ans[i] << "\n";
    }

    return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 49