fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Check if we can make a team of size sz
  5. bool check(int sz, vector<int>& lo, vector<int>& hi) {
  6.     int n = lo.size() - 1;
  7.  
  8.     // Find valid position range for each person
  9.     vector<pair<int, int>> ranges;
  10.  
  11.     for (int i = 1; i <= n; i++) {
  12.         // Calculate which positions person i can take
  13.         int l = max(1, sz - hi[i]);
  14.         int r = min(sz, lo[i] + 1);
  15.  
  16.         if (l <= r) {
  17.             ranges.push_back({l, r});
  18.         }
  19.     }
  20.  
  21.     // Need at least sz people with valid ranges
  22.     if (ranges.size() < sz) return false;
  23.  
  24.     // Sort by start position
  25.     sort(ranges.begin(), ranges.end());
  26.  
  27.     // Min heap to pick person whose range ends earliest
  28.     priority_queue<int, vector<int>, greater<int>> pq;
  29.     int id = 0;
  30.  
  31.     // Fill each position greedily
  32.     for (int p = 1; p <= sz; p++) {
  33.         // Add all people who can start at position p
  34.         while (id < ranges.size() && ranges[id].first <= p) {
  35.             pq.push(ranges[id].second);
  36.             id++;
  37.         }
  38.  
  39.         // Remove people who can't be at position p anymore
  40.         while (!pq.empty() && pq.top() < p) {
  41.             pq.pop();
  42.         }
  43.  
  44.         // No one available for this position
  45.         if (pq.empty()) return false;
  46.  
  47.         // Assign someone to position p
  48.         pq.pop();
  49.     }
  50.  
  51.     return true;
  52. }
  53.  
  54. int main() {
  55.     ios::sync_with_stdio(false);
  56.     cin.tie(nullptr);
  57.  
  58.     int n;
  59.     cin >> n;
  60.  
  61.     vector<int> lo(n + 1), hi(n + 1);
  62.  
  63.     for (int i = 1; i <= n; i++) cin >> lo[i];
  64.     for (int i = 1; i <= n; i++) cin >> hi[i];
  65.  
  66.     // Binary search on answer
  67.     int l = 0, r = n;
  68.  
  69.     while (l < r) {
  70.         int m = (l + r + 1) / 2;
  71.  
  72.         if (check(m, lo, hi)) {
  73.             l = m;  // Try bigger
  74.         } else {
  75.             r = m - 1;  // Try smaller
  76.         }
  77.     }
  78.  
  79.     cout << l << "\n";
  80.  
  81.     return 0;
  82. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/IUY34q
language:
C++14 (gcc 8.3)
created:
4 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!