Submission #743794

#TimeUsernameProblemLanguageResultExecution timeMemory
743794JellyTheOctopusExhibition (JOI19_ho_t2)C++17
100 / 100
238 ms5340 KiB
#include <bits/stdc++.h> using namespace std; #define f first #define s second int N, M; vector<pair<int, int>> pictures; vector<int> frames; bool check(int x) { int j = 1; int prev = 0; bool flag = true; priority_queue<int, vector<int>, greater<int>> pq; for (int i = M-x+1; i <= M; i++) { while (j <= N && pictures[j].f <= frames[i]) { pq.push(pictures[j].s); j++; } if (pq.empty()) { flag = false; } else { while (!pq.empty() && (pq.top() < prev)) { pq.pop(); } if (pq.empty()) { flag = false; } else { prev = pq.top(); pq.pop(); } } } return flag; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> N >> M; pictures.resize(N+1); frames.resize(M+1); for (int i = 1; i <= N; i++) { cin >> pictures[i].f >> pictures[i].s; } for (int i = 1; i <= M; i++) { cin >> frames[i]; } sort(pictures.begin(), pictures.end()); sort(frames.begin(), frames.end()); int high = min(N, M); int low = 1; int ans = low-1; while (low <= high) { int mid = (low+high)/2; if (check(mid)) { ans = mid; low = mid+1; } else { high = mid-1; } } cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...