Submission #99705

#	Time	Username	Problem	Language	Result	Execution time	Memory
99705		MrTEK	Exhibition (JOI19_ho_t2)	C++14	100 / 100	89 ms	2316 KiB

joi2019_ho_t2

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int,int> ii;

const int N = 1e5 + 5;

int n,m;
ii a[N];
int c[N];
vector <int> v;

bool check(int x) {
  v.clear();
  for (int i = 1 ; i <= x ; i++)
    v.push_back(c[i]);
  for (int i = 1 ; i <= n ; i++) {
    if (v.empty())
      return true;
    if (a[i].second <= v.back())
      v.pop_back();
  }
  return v.empty();
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin >> n >> m;
  for (int i = 1 ; i <= n ; i++)
    cin >> a[i].second >> a[i].first;
  for (int i = 1 ; i <= m ; i++)
    cin >> c[i];
  sort(a + 1,a + n + 1);
  sort(c + 1,c + m + 1,greater <int>());
  int l = 0, r = m;
  while(l < r) {
    int mid = (l + r + 1) / 2;
    if (check(mid))
      l = mid;
    else
      r = mid - 1;
  }
  cout << l << endl;
}

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