oj.uz

Submission #912572

# Submission time Handle Problem Language Result Execution time Memory
912572 2024-01-19T15:55:13 Z ByeWorld Exhibition (JOI19_ho_t2) C++14
0 / 100
 1 ms 348 KB 
#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) break;
        if(val[idx].se <= x[i]){
            cnt++; idx++;
        }
    }
    if(cnt == p) return 1;
    return 0;
}

int bin(){
    int ans = 0;
    for(int i=min(n, m); i>=1; i--){
        if(cek(i)){
            ans = i;
            break;
        }
    }
    return ans;
}
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";

    cout << bin() << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -