Advertisement
Guest User

Untitled

a guest
Jul 19th, 2018
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.11 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #pragma GCC optimize ("O3")
  3.  
  4. using namespace std;
  5. using ll = long long;
  6.  
  7. ll get(ll l, ll r) {
  8. return max(0LL, r - l - 1LL);
  9. }
  10.  
  11. int main() {
  12. freopen("a.in", "r", stdin), freopen("a.out", "w", stdout);
  13. ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  14. int n;
  15. cin >> n;
  16. vector<pair<ll, int>> a;
  17. map<ll, bool> used;
  18. for (int i = 0; i < n; ++i) {
  19. ll l, r;
  20. cin >> l >> r;
  21. a.push_back({l, -1});
  22. a.push_back({r, 1});
  23. }
  24. sort(a.begin(), a.end());
  25. for (int i = 0; i < 2 * n; ++i) {
  26. cout << a[i].first << " " << a[i].second << endl;
  27. }
  28. vector<ll> ans(n + 1);
  29. ll last = a[0].first;
  30. int bal = 0;
  31. for (int i = 0; i < 2 * n; ++i) {
  32. if (a[i].second == -1) {
  33. ans[bal] += get(last, a[i].first);
  34. used[a[i].first] = true;
  35. ++bal;
  36. } else {
  37. if (!used[a[i].first]) {
  38. used[a[i].first] = true;
  39.  
  40. }
  41. --bal;
  42. }
  43. last = a[i].first;
  44. }
  45. return 0;
  46. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement