Submission #1150529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150529		koukirocks	Exhibition (JOI19_ho_t2)	C++20	100 / 100	66 ms	1872 KiB

joi2019_ho_t2

#include<bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) x.begin()+1, x.end()
#define F first
#define S second

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

struct BIT {
    int n;
    vector<int> a;
    BIT(int _n):n(_n) {
        a.resize(n+1);
    }
    void update(int x,int v) {
        while (x<=n) {
            a[x]=max(a[x],v);
            x+=(-x&x);
        }
    }
    int query(int x) {
        // cout<<x<<" x\n"<<flush;
        int ans=0;
        while (x) {
            ans=max(ans,a[x]);
            x-=(-x&x);
        }
        return ans;
    }
};

int main() {
    speed;
    int n,m;
    cin>>n>>m;
    vector<pii> pt(n+1);
    vector<int> fm(m+1);
    for (int i=1;i<=n;i++) {
        cin>>pt[i].S>>pt[i].F;
    }
    sort(all(pt));
    for (int i=1;i<=m;i++) {
        cin>>fm[i];
    }
    sort(all(fm));
    for (int i=1;i<=n;i++) {
        pt[i].S=lower_bound(all(fm),pt[i].S)-fm.begin();
        pt[i].S=m-pt[i].S+1;
        // cout<<pt[i].S<<" pt\n"<<flush;
    }
    BIT b(m);
    for (int i=n;i>=1;i--) {
        if (pt[i].S==0) continue;
        int mx=b.query(pt[i].S-1);
        int l=0,r=pt[i].S-1;
        while (l<r) {
            int mid=l+r>>1;
            if (b.query(mid)==mx) r=mid;
            else l=mid+1;
        }
        b.update(l+1,mx+1);
    }
    cout<<b.query(m)<<"\n";
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50