Submission #1221392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221392		12345678	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	964 ms	78284 KiB

matryoshka

#include <bits/stdc++.h>

using namespace std;

const int nx=4e5+5;

int n, q, a[nx], b[nx], r[nx], h[nx], tx, ty, res[nx];
map<int, int> mpx, mpy;
vector<int> add[nx], qrs[nx];

struct segtree
{
    int d[4*nx];
    void update(int l, int r ,int i, int idx, int vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i]=max(d[i], vl), void();
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return 0;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>q;
    for (int i=1; i<=n; i++) cin>>a[i]>>b[i], mpx[a[i]]=mpy[b[i]]=0;
    for (int i=1; i<=q; i++) cin>>r[i]>>h[i], mpx[r[i]]=mpy[h[i]]=0;
    for (auto &[x, y]:mpx) y=++tx;
    for (auto &[x, y]:mpy) y=++ty;
    for (int i=1; i<=n; i++) add[mpy[b[i]]].push_back(mpx[a[i]]);
    for (int i=1; i<=q; i++) qrs[mpy[h[i]]].push_back(i);
    for (int i=1; i<=n+q; i++)
    {
        sort(add[i].begin(), add[i].end());
        reverse(add[i].begin(), add[i].end());
        for (auto x:add[i]) s.update(1, n+q, 1, x, s.query(1, n+q, 1, x, n+q)+1);
        for (auto idx:qrs[i]) res[idx]=s.query(1, n+q, 1, mpx[r[idx]], n+q);
    }
    for (int i=1; i<=q; i++) cout<<res[i]<<'\n';
}

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