fork download
copy 
  1. // @check-accepted: task
  2.  
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <set>
  7. using namespace std;
  8. using ii = pair<int,int>;
  9.  
  10. int test(const vector<ii> &m, int c) {
  11.     set<ii> active;
  12.     int del = 0;
  13.  
  14.     for(int i = 0; i < m.size(); ++i) {
  15.         while(!active.empty() && active.begin()->first < m[i].first) active.erase(active.begin());
  16.         active.insert(ii(m[i].second, i));
  17.         if(active.size() > c) {
  18.             active.erase(prev(active.end()));
  19.             ++del;
  20.         }
  21.     }
  22.  
  23.     return del;
  24. }
  25.  
  26. int main() {
  27.     int N, K;
  28.     cin >> N >> K;
  29.     vector<ii> m(N);
  30.     for(ii &x: m) cin >> x.first >> x.second;
  31.  
  32.     sort(m.begin(), m.end());
  33.  
  34.     int lb = 0, ub = N;
  35.     while(lb < ub) {
  36.         int mid = (lb + ub) / 2;
  37.         if(test(m, mid) <= K) {
  38.             ub = mid;
  39.         } else {
  40.             lb = mid + 1;
  41.         }
  42.     }
  43.  
  44.     cout << lb << "\n";
  45.  
  46.     return 0;
  47. }
  48.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
3 1
5 12
2 8
6 15
stdout
copy 
2
https://ideone.com/CoYtLx
language:
C++ (gcc 8.3)
created:
6 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!