fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Problem: Each person i has range [lo[i], hi[i]] of people worse than them
  5. // Find maximum team size where everyone's constraints are satisfied
  6.  
  7. // Check if we can make a valid team of size sz
  8. bool check(int sz, vector<int>& lo, vector<int>& hi) {
  9.     int n = lo.size() - 1;
  10.  
  11.     // For person i in a team of size sz:
  12.     // - lo[i] people worse means i is at position lo[i]+1 or better
  13.     // - hi[i] people worse means i is at position sz-hi[i] or worse
  14.  
  15.     // Find valid position range [l, r] for each person in team of size sz
  16.     vector<pair<int, int>> ranges;
  17.  
  18.     for (int i = 1; i <= n; i++) {
  19.         // Left bound: at least sz-hi[i] position (not too good)
  20.         int l = max(1, sz - hi[i]);
  21.         // Right bound: at most lo[i]+1 position (not too bad)
  22.         int r = min(sz, lo[i] + 1);
  23.  
  24.         // Only include if valid range exists
  25.         if (l <= r) {
  26.             ranges.push_back({l, r});
  27.         }
  28.     }
  29.  
  30.     // Need at least sz people with valid ranges
  31.     if (ranges.size() < sz) return false;
  32.  
  33.     // Sort by earliest possible position (greedy assignment)
  34.     sort(ranges.begin(), ranges.end());
  35.  
  36.     // Min heap: tracks rightmost position each available person can take
  37.     // We pick person whose range ends earliest (greedy choice)
  38.     priority_queue<int, vector<int>, greater<int>> pq;
  39.     int id = 0;
  40.  
  41.     // Try to fill positions 1, 2, ..., sz
  42.     for (int p = 1; p <= sz; p++) {
  43.         // Add all people who can start at position p or earlier
  44.         while (id < ranges.size() && ranges[id].first <= p) {
  45.             pq.push(ranges[id].second);  // store their right bound
  46.             id++;
  47.         }
  48.  
  49.         // Remove people whose range has already passed
  50.         while (!pq.empty() && pq.top() < p) {
  51.             pq.pop();
  52.         }
  53.  
  54.         // No one available for this position
  55.         if (pq.empty()) return false;
  56.  
  57.         // Assign the person with earliest ending range to position p
  58.         pq.pop();
  59.     }
  60.  
  61.     return true;
  62. }
  63.  
  64. int main() {
  65.     ios::sync_with_stdio(false);
  66.     cin.tie(nullptr);
  67.  
  68.     int n;
  69.     cin >> n;
  70.  
  71.     // lo[i] = minimum number of people worse than person i
  72.     // hi[i] = maximum number of people worse than person i
  73.     vector<int> lo(n + 1), hi(n + 1);
  74.  
  75.     for (int i = 1; i <= n; i++) cin >> lo[i];
  76.     for (int i = 1; i <= n; i++) cin >> hi[i];
  77.  
  78.     // Binary search on maximum team size
  79.     int l = 0, r = n;
  80.  
  81.     while (l < r) {
  82.         int m = (l + r + 1) / 2;
  83.  
  84.         if (check(m, lo, hi)) {
  85.             l = m;  // Can make team of size m, try bigger
  86.         } else {
  87.             r = m - 1;  // Cannot make team of size m, try smaller
  88.         }
  89.     }
  90.  
  91.     cout << l << "\n";
  92.  
  93.     return 0;
  94. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
1
https://ideone.com/YWG7lg
language:
C++14 (gcc 8.3)
created:
3 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!