fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxn = 2e5 + 5;
  4. #define int long long
  5. struct BIT{
  6. 	int n;
  7. 	vector<int> bit;
  8. 	BIT(int n = 0) : n(n), bit(n + 5, 0){};
  9. 	void update(int i)
  10. 	{
  11. 		for(; i <= n; i += (-i & i)) bit[i]++;
  12. 	}
  13. 	int get(int i)
  14. 	{
  15. 		int res = 0;
  16. 		for(; i; i -= (-i & i)) res += bit[i];
  17. 		return res;
  18. 	}
  19. } B;
  20. int n, ans = 1;
  21. pair<int, int> a[maxn];
  22. int32_t main()
  23. {
  24. 	ios_base::sync_with_stdio(0);
  25. 	cin.tie(0);
  26. 	if(fopen("cake.inp", "r"))
  27. 	{
  28. 		freopen("cake.inp", "r", stdin);
  29. 		freopen("cake.out", "w", stdout);
  30. 	}
  31. 	cin >> n;
  32. 	for(int i = 1; i <= n; i++) 
  33. 	{
  34. 		cin >> a[i].first >> a[i].second;
  35. 		if(a[i].first > a[i].second) swap(a[i].first, a[i].second);
  36. 	}
  37. 	sort(a + 1, a + n + 1);
  38. 	B = BIT(n * 2);
  39. 	for(int i = 1; i <= n; i++)
  40. 	{
  41. 		// cout << B.get(a[i].second) - B.get(a[i].first) + 1 << '\n';
  42. 		ans += B.get(a[i].second) - B.get(a[i].first) + 1;
  43. 		B.update(a[i].second);
  44. 	}
  45. 	cout << ans;
  46. 	return 0;
  47. }
Success #stdin #stdout 0s 5340KB
comments (?)
stdin
copy 
3
1 4
2 5
3 6
stdout
copy 
7
https://ideone.com/c3r0Tm
language:
C++ (gcc 8.3)
created:
8 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!