Submission #842328

#	Time	Username	Problem	Language	Result	Execution time	Memory
842328		c2zi6	Matryoshka (JOI16_matryoshka)	C++14	0 / 100	0 ms	348 KiB

matryoshka

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

class SEGMENTTREE {
private:
    int n;
    vector<int> tree;
    int update(int N, int L, int R, int i, int x) {
        if (i < L || i > R) return tree[N];
        if (L == R) return tree[N] = max(x, tree[N]);
        int M = (L + R) / 2;
        return tree[N] = max(update(2*N+1, L, M, i, x), update(2*N+2, M+1, R, i, x));
    }
    int get(int N, int L, int R, int l, int r) {
        if (l <= L && R <= r) return tree[N];
        if (R < l || L > r) return 0;
        int M = (L + R) / 2;
        return max(get(2*N+1, L, M, l, r), get(2*N+2, M+1, R, l, r));
    }
public:
    void print() {
        for (int i = 0; i < n; i++) cout << get(0, 0, n-1, i, i) << " ";
        cout << endl;
    }
    SEGMENTTREE(int m) {
        n = 1;
        while (n < m) n <<= 1;
        tree = vector<int>(2 * n);
    }
    int GEQ(int x) {
        return get(0, 0, n-1, x, n-1);
    }
    void upd(int h, int v) {
        update(0, 0, n-1, h, v);
    }
};

struct MATR {
    int r, h;
    bool operator<(const MATR& b) {
        if (this->h == b.h) return this->r > b.r;
        return this->h < b.h;
    }
};

struct QUERY {
    int A, B, i;
    bool operator<(const QUERY& b) {
        return this->B < b.B;
    }
};

/**
  r >= a
  h <= b
*/

int main() {
    int n, q;
    cin >> n >> q;
    vector<MATR> a(n);
    for (int i = 0; i < n; i++) cin >> a[i].r >> a[i].h;
    vector<QUERY> qrs(q);
    for (int i = 0; i < q; i++) cin >> qrs[i].A >> qrs[i].B, qrs[i].i = i;

    /* compress */ {
        map<int, int> cor;
        for (int i = 0; i < n; i++) cor[a[i].r] = 0;
        for (int i = 0; i < q; i++) cor[qrs[i].A] = 0;
        int ind = 0; for (pair<int, int> p : cor) cor[p.first] = ind++;
        for (int i = 0; i < n; i++) a[i].r = cor[a[i].r];
        for (int i = 0; i < q; i++) qrs[i].A = cor[qrs[i].A];
    }

    sort(a.begin(), a.end());
    sort(qrs.begin(), qrs.end());

    for (int i = 0; i < q; i++) cout << i << " ";
    cout << endl;
    return 0;
    
    vector<int> ans(q);
    SEGMENTTREE seg(n + q);
    for (int i = 0, j = 0; i < q; i++) {
        while (a[j].h <= qrs[i].B) {
            seg.upd(a[j].r, seg.GEQ(a[j].r)+1);
            j++;
        }
        ans[qrs[i].i] = seg.GEQ(qrs[i].A);
    }
    for (int x : ans) cout << x << endl;
}

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