fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long
  6. #define fi first
  7. #define se second
  8. #define oo 1000000000000000000LL
  9. #define pb push_back
  10. #define ii pair<int, int>
  11. #define iii pair<int, ii>
  12. #define BIT(mask, i) ((mask) >> (i) & 1)
  13. #define MASK(i) (1LL << (i))
  14. #define TASK "TEST"
  15.  
  16. const int N = 200005;
  17.  
  18. int n, m, ans;
  19. int f[N];
  20. map<int, int> mp;
  21. vector<int> v;
  22.  
  23. /// a[pos] += val
  24. void update(int pos, int val) {
  25.     for (int i = pos; i <= m; i += i & -i) f[i] += val;
  26. }
  27.  
  28. /// a[1] + a[2] + ... + a[pos]
  29. int get(int pos) {
  30.     int res = 0;
  31.     for (int i = pos; i; i -= i & -i) res += f[i];
  32.     return res;
  33. }
  34.  
  35. int sum(int l, int r) {
  36.     return get(r) - get(l - 1);
  37. }
  38.  
  39. void calc(int l, int r) {
  40.     if (l <= r) {
  41.         int cnt = upper_bound(v.begin(), v.end(), r) - lower_bound(v.begin(), v.end(), l);
  42.         ans += r - l + 1 - cnt;
  43.     }
  44. }
  45.  
  46. signed main() {
  47.     ios_base::sync_with_stdio(0);
  48.     cin.tie(0); cout.tie(0);
  49.  
  50.     if (fopen(TASK".INP", "r")) {
  51.         freopen(TASK".INP", "r", stdin);
  52.         freopen(TASK".OUT", "w", stdout);
  53.     }
  54.  
  55.     cin >> n;
  56.  
  57.     for (int i = 1; i <= n; i++) {
  58.         int a, b;
  59.         cin >> a >> b;
  60.  
  61.         int u = (mp[a] == 0 ? a : mp[a]), v = (mp[b] == 0 ? b : mp[b]);
  62.         mp[b] = u;
  63.         mp[a] = v;
  64.     }
  65.  
  66.     for (ii e : mp) v.pb(e.se);
  67.  
  68.     sort(v.begin(), v.end());
  69.     m = v.size();
  70.  
  71.     for (ii e : mp) {
  72.         int pos = e.fi, val = e.se, x = lower_bound(v.begin(), v.end(), val) - v.begin() + 1;
  73.  
  74.         calc(val + 1, pos - 1);
  75.         calc(pos + 1, val - 1);
  76.  
  77.         ans += sum(x + 1, m);
  78.         update(x, 1);
  79.     }
  80.  
  81.     cout << ans;
  82. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4v8TlS
language:
C++14 (gcc 8.3)
created:
2 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!