제출 #912597

#제출 시각아이디문제언어결과실행 시간메모리
912597ByeWorldExhibition (JOI19_ho_t2)C++14
100 / 100
60 ms6768 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#define bupol __builtin_popcount
#define int long long 
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 2e5+5;
const int MAXK = 205;
const int LOG = 20;
const int MOD = 1e9+7;
const int SQRT = 520;
const int INF = 1e18+10;
const int INF2 = 1e18;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> ipii;
bool cmp(pii a, pii b){
    if(a.fi==b.fi) return a.se > b.se;
    return a.fi > b.fi;
}
int n, m;
vector <int> x;
vector <pii> val;

bool cek(int p){
    int idx = 1, i=1, cnt = 0;
    for(i=1; i<=p; i++){
        while(idx<=n && val[idx].se > x[i]){
            idx++;
            continue; // lebih gede
        }
        //if(p==2) cout << idx << " idx\n";
        if(idx<=n && val[idx].se <= x[i]){
            cnt++; idx++;
        }
    }
    if(cnt == p) return 1;
    return 0;
}

void bin(){
    int l=1, r=min(n, m), ans = 0;
    while(l<=r){
        int mid = ((l+r)>>1);
        if(cek(mid)){
            ans = mid;
            l = mid+1;
        } else {
            r = mid-1;
        }
    }
    cout << ans << '\n';
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        int a, b; cin >> a >> b;
        val.pb({b, a});
    }
    val.pb({INF, INF});
    sort(val.begin(), val.end(), cmp);
    for(int i=1; i<=m; i++){
        int pp; cin >> pp; x.pb(pp);
    }
    sort(x.begin(), x.end()); x.pb(-1);
    reverse(x.begin(), x.end());

    // for(auto in : val) cout << in.fi << ' '<< in.se << " in\n";
    // for(auto in : x) cout << in << " pp\n";
    bin();

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...