Submission #775880

#	Time	Username	Problem	Language	Result	Execution time	Memory
775880		gun_gan	Exhibition (JOI19_ho_t2)	C++17	100 / 100	49 ms	4932 KiB

joi2019_ho_t2

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

const int MX = 1e5 + 7;
int N, M;

vector<pair<int, int>> pic;
vector<int> frame;

bool can(int x) {
      int k = M - x;
      for(int i = 0; i < N; i++) {
            if(pic[i].second <= frame[k]) k++;
            if(k == M) return 1;
      }

      return 0;
}

int main() {
      cin.tie(0); ios_base::sync_with_stdio(0);
      
      cin >> N >> M;
      for(int i = 0; i < N; i++) {
            int x, y;
            cin >> x >> y;

            pic.push_back({y, x});
      }

      sort(pic.begin(), pic.end());

      for(int i = 0; i < M; i++) {
            int c;
            cin >> c;

            frame.push_back(c);
      }

      sort(frame.begin(), frame.end());

      int l = 1, r = min(M, N), ans = 0;
      while(l <= r) {
            int mid = (l + r) >> 1;
            if(can(mid)) {
                  l = mid + 1, ans = mid;
            } else {
                  r = mid - 1;
            }
      }

      cout << ans << '\n';
}

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