제출 #233949

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
233949		nicolaalexandra	Exhibition (JOI19_ho_t2)	C++14	100 / 100	222 ms	4984 KiB

joi2019_ho_t2

#include <bits/stdc++.h>
#define DIM 100010
using namespace std;
pair <int,int> v[DIM];
int w[DIM],poz[DIM];
int n,m,i;
int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m;
    for (i=1;i<=n;i++)
        cin>>v[i].second>>v[i].first;

    for (i=1;i<=m;i++)
        cin>>w[i];

    sort (w+1,w+m+1);
    sort (v+1,v+n+1);

    for (i=1;i<=n;i++){
        int st = 1, dr = m, sol = m+1;
        while (st <= dr){
            int mid = (st+dr)>>1;
            if (w[mid] >= v[i].second){
                sol = mid;
                dr = mid-1;
            } else st = mid+1;
        }

        poz[i] = sol;

    }

    int idx = n, sol = 0;
    for (i=m;i && idx;i--){
        while (idx >= 1 && poz[idx] > i)
            idx--;

        if (idx){
            sol++;
            idx--;
        }
    }

    cout<<sol;

    return 0;
}

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