fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. const int N = 1e5 + 5;
  6. int l[N], r[N], point[N];
  7. signed main() {
  8.     ios_base::sync_with_stdio(false);
  9.     cin.tie(NULL), cout.tie(NULL);
  10.     int n, m;
  11.     cin >> n >> m;
  12.     vector<int> v;
  13.     v.push_back(1);
  14.     v.push_back(n + 1);
  15.     for(int i = 1; i <= m; ++i) {
  16.         cin >> l[i] >> r[i];
  17.         v.push_back(l[i]);
  18.         v.push_back(r[i] + 1);
  19.     }
  20.     sort(v.begin(), v.end());
  21.     v.erase(unique(v.begin(), v.end()), v.end());
  22.     for(int i = 1; i <= m; ++i) {
  23.         if(l[i] <= r[i]) {
  24.             int lx = lower_bound(v.begin(), v.end(), l[i]) - v.begin();
  25.             int rx = lower_bound(v.begin(), v.end(), r[i] + 1) - v.begin();
  26.             point[lx]++, point[rx]--;
  27.         } else {
  28.             int lx = lower_bound(v.begin(), v.end(), l[i]) - v.begin();
  29.             int rx = lower_bound(v.begin(), v.end(), n + 1) - v.begin();
  30.             point[lx]++, point[rx]--;
  31.             lx = lower_bound(v.begin(), v.end(), 1) - v.begin();
  32.             rx = lower_bound(v.begin(), v.end(), r[i] + 1) - v.begin();
  33.             point[lx]++, point[rx]--;
  34.         }
  35.     }
  36.     int cur = 0, mx = 0, cnt = 0;
  37.     for(int i = 0; i < v.size() - 1; ++i) {
  38.         cur += point[i];
  39.         ll len = v[i + 1] - v[i];
  40.         if(len <= 0) continue;
  41.         if(cur > mx) mx = cur, cnt = len;
  42.         else if(cur == mx) cnt += len;
  43.     }
  44.     cout << mx << ' ' << cnt;
  45.     return 0;
  46. }
  47.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
6 3
1 5
4 2
1 6
stdout
copy 
3 4
https://ideone.com/QGUdaz
language:
C++ (gcc 8.3)
created:
3 days 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!