Submission #728726

#	Time	Username	Problem	Language	Result	Execution time	Memory
728726		abcvuitunggio	Matryoshka (JOI16_matryoshka)	C++17	100 / 100	243 ms	15356 KiB

matryoshka

#include <bits/stdc++.h>
using namespace std;
struct query{
    int a,b,idx;
}a[200001];
struct doll{
    int r,h;
}d[200001];
int n,q,res[200001],f[200001];
vector <int> v;
void update(int i, int val){
    for (;i<=n;i+=i&(-i))
        f[i]=max(f[i],val);
}
int get(int i){
    int res=0;
    for (;i;i-=i&(-i))
        res=max(res,f[i]);
    return res;
}
int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> q;
    for (int i=1;i<=n;i++){
        cin >> d[i].r >> d[i].h;
        v.push_back(d[i].h);
    }
    sort(d+1,d+n+1,[](doll a, doll b){return (a.r<b.r||(a.r==b.r&&a.h>b.h));});
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(),v.end())-v.begin());
    for (int i=1;i<=q;i++){
        cin >> a[i].a >> a[i].b;
        a[i].idx=i;
    }
    sort(a+1,a+q+1,[](query a, query b){return a.a>b.a;});
    int j=n;
    for (int i=1;i<=q;i++){
        for (;j&&d[j].r>=a[i].a;j--){
            int pos=lower_bound(v.begin(),v.end(),d[j].h)-v.begin()+1;
            update(pos,get(pos)+1);
        }
        res[a[i].idx]=get(upper_bound(v.begin(),v.end(),a[i].b)-v.begin());
    }
    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