Submission #1221388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221388		12345678	Matryoshka (JOI16_matryoshka)	C++20	51 / 100	2093 ms	4128 KiB

matryoshka

#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;

int n, q, a[nx], b[nx], r, h;

struct doll
{
    int a, b;
    bool operator < (const doll &o) const {return a==o.a?b<o.b:a<o.a;}
    doll(int a, int b): a(a), b(b){}
};
vector<doll> v;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>q;
    for (int i=1; i<=n; i++) cin>>a[i]>>b[i];
    while (q--)
    {
        cin>>r>>h;
        v.clear();
        for (int i=1; i<=n; i++) if (r<=a[i]&&b[i]<=h) v.push_back(doll(a[i], -b[i]));
        sort(v.begin(), v.end());
        vector<int> lis;
        for (auto x:v)
        {
            auto itr=upper_bound(lis.begin(), lis.end(), x.b);
            if (itr==lis.end()) lis.push_back(x.b);
            else *itr=x.b;
        } 
        cout<<lis.size()<<'\n';
    }

}

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