Submission #1307218

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

matryoshka

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

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

struct Doll {
    int R, H;
};

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

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

int fenwick[MAXN + MAXQ + 2];
int sizeFenwick;

void fenwick_update(int idx, int val) {
    while (idx <= sizeFenwick) {
        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;
        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());
    sizeFenwick = values.size();

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

    vector<int> idx(N);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.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;
    });

    vector<int> qidx(Q);
    iota(qidx.begin(), qidx.end(), 0);
    sort(qidx.begin(), qidx.end(), [&](int i, int j) {
        return queries[i].A > queries[j].A;
    });

    fill(fenwick, fenwick + sizeFenwick + 1, 0);

    int ptr = 0;
    for (int qi = 0; qi < Q; ++qi) {
        int q = qidx[qi];
        int A = queries[q].A;
        while (ptr < N && dolls[idx[ptr]].R >= A) {
            int curR = dolls[idx[ptr]].R;
            vector<pair<int, int>> group;
            while (ptr < N && dolls[idx[ptr]].R == curR) {
                int i = idx[ptr];
                group.emplace_back(rankH[i], i);
                ++ptr;
            }
            vector<int> gvals(group.size());
            for (size_t k = 0; k < group.size(); ++k) {
                int h = group[k].first;
                gvals[k] = fenwick_query(h) + 1;
            }
            for (size_t k = 0; k < group.size(); ++k) {
                int h = group[k].first;
                fenwick_update(h, gvals[k]);
            }
        }
        ans[q] = fenwick_query(rankB[q]);
    }

    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