Submission #825903

#	Time	Username	Problem	Language	Result	Execution time	Memory
825903		dijbkr	Exhibition (JOI19_ho_t2)	C++14	100 / 100	49 ms	5644 KiB

joi2019_ho_t2

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll n,m;
pair<ll,ll>p[200005];
ll a[200005];

bool check(ll x) {
   ll pos=m-x+1;
   for (ll i=1; i<=n; i++) {
      if (p[i].second<=a[pos]) {
         pos++;
         if (pos==m+1) {
            return true;
         }
      }
   }
   return false;
}

ll bs() {
   ll ans=0;
   ll l=1;
   ll r=min(m,n);
   while (l<=r) {
      ll mid=(l+r)/2;
      if (check(mid)) {
         ans=mid;
         l=mid+1;
      } else {
         r=mid-1;
      }
   }
   return ans;
}

int main() {
   ios_base::sync_with_stdio(false);
   cin.tie(NULL); cout.tie(NULL);
   cin >> n >> m;
   for (ll i=1; i<=n; i++) {
      cin >> p[i].second >> p[i].first;
   }
   sort(p+1,p+n+1);
   for (ll i=1; i<=m; i++) {
      cin >> a[i];
   }
   sort(a+1,a+m+1);
   cout << bs();
}

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