Submission #1156934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156934		dnnnda	Exhibition (JOI19_ho_t2)	C++20	0 / 100	0 ms	328 KiB

joi2019_ho_t2

#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define ll long long
//#define int long long
//#pragma GCC optimize("Ofast, unroll-loop")
//#pragma GCC target("avx,avx2")
#pragma GCC optimize("O3")
const int inf=0x3f3f3f3f;
const ll inff=0x3f3f3f3f3f3f3f3f;
//const int X=1000000007;
const int X=998244353;

pair<int,int> p[100005];
int f[100005], id[100005], lb[100005], mx=0, mn=inf;

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i=0 ; i<n ; i++) cin >> p[i].F >> p[i].S;
    for(int i=0 ; i<m ; i++) cin >> f[i];
    for(int i=0 ; i<n ; i++) mn=min(mn,p[i].F);
    for(int i=0 ; i<m ; i++) mx=max(mx,f[i]);
    if(mx<mn){
        cout << "0\n";
        return 0;
    }
    sort(p,p+n,[](pair<int,int> a, pair<int,int> b){
         if(a.S==b.S) return a.F<b.F;
         return a.S<b.S;
    });
    sort(f,f+m);
    //for(int i=0 ; i<m ; i++) cout << f[i] << (i==m-1 ? '\n' : ' ');
    //for(int i=0 ; i<n ; i++) cout << p[i].F << ',' << p[i].S << ' ';
    //cout << '\n';
    //f.erase(unique(f.begin(),f.end()),f.end());
    lb[0]=id[0]=(lower_bound(f,f+m,p[0].F)-f);
    for(int i=1 ; i<n ; i++) lb[i]=lower_bound(f,f+m,p[i].F)-f;
    //for(int i=0 ; i<n ; i++) cout << id[i] << ' ';
    //cout << '\n';
    vector<int> v{id[0]};
    for(int i=1 ; i<n ; i++){
        if(lb[i]==lb[i-1]&&id[i-1]+1<m&&f[id[i-1]+1]>=p[i].F) id[i]=id[i-1]+1;
        else id[i]=lb[i];

        if(id[i]>v.back()) v.push_back(id[i]);
        else *lower_bound(v.begin(),v.end(),id[i])=id[i];
        //for(int j:v) cout << j << ' ';
        //cout << '\n';
    }
    cout << v.size() << '\n';


    return 0;
}

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