Submission #1307139

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

matryoshka

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

const int MAXN = 200000;
const int MAXQ = 200000;

struct Doll {
    int R, H, id;
};

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

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

int fenwick[MAXN + MAXQ + 2];

void fenwick_update(int idx, int val) {
    while (idx <= (int)values.size()) {
        fenwick[idx] = max(fenwick[idx], val);
        idx += idx & -idx;
    }
}

int fenwick_query(int idx) {
    int res = 0;
    while (idx > 0) {
        res = max(res, fenwick[idx]);
        idx -= idx & -idx;
    }
    return res;
}

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

    cin >> N >> Q;
    for (int i = 0; i < N; ++i) {
        cin >> dolls[i].R >> dolls[i].H;
        dolls[i].id = i;
        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());

    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) {
        int idx = upper_bound(values.begin(), values.end(), queries[i].B) - values.begin();
        compB[i] = idx;
    }

    sort(dolls, dolls + N, [](const Doll& a, const Doll& b) {
        if (a.R != b.R) return a.R > b.R;
        return a.H > b.H;
    });

    sort(queries, queries + Q, [](const Query& a, const Query& b) {
        return a.A > b.A;
    });

    int ptr = 0;
    for (int i = 0; i < Q; ++i) {
        while (ptr < N && dolls[ptr].R >= queries[i].A) {
            int h = compH[dolls[ptr].id];
            int cur = 1 + fenwick_query(h);
            fenwick_update(h, cur);
            ++ptr;
        }
        ans[queries[i].id] = fenwick_query(compB[queries[i].id]);
    }

    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