fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. #include <ext/pb_ds/tree_policy.hpp>
  6. using namespace __gnu_pbds;
  7. template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  8.  
  9. #define ll long long
  10. #define ar array
  11.  
  12. const int mxN=1e5;
  13. int n, xl[mxN], xr[mxN];
  14.  
  15. struct event {
  16. 	int x, type, y;
  17. 	bool operator<(const event &o) {
  18. 		return make_pair(x, type)<make_pair(o.x, o.type);
  19. 	}
  20. };
  21.  
  22. void solve() {
  23. 	//input
  24. 	cin >> n;
  25. 	for(int i=0; i<n; ++i)
  26. 		cin >> xl[i] >> xr[i];
  27.  
  28. 	//find the longest segments from overlaps
  29. 	map<int, int> mpl, mpr;
  30. 	for(int i=0; i<n; ++i) {
  31. 		if(mpl.find(xl[i])==mpl.end())
  32. 			mpl[xl[i]]=xr[i];
  33. 		else
  34. 			mpl[xl[i]]=max(xr[i], mpl[xl[i]]);
  35. 		if(mpr.find(xr[i])==mpr.end())
  36. 			mpr[xr[i]]=xl[i];
  37. 		else
  38. 			mpr[xr[i]]=min(xl[i], mpr[xr[i]]);
  39. 	}
  40.  
  41. 	//create the events
  42. 	vector<event> ve;
  43. 	for(auto a : mpr) {
  44. 		//xl[i] = a.second, xr[i] = a.first
  45. 		//right segment i should be active in [xl[i], xr[i])
  46. 		//add this right segment at time xl[i]
  47. 		ve.push_back({a.second, 1, a.first});
  48. 		//remove this right segment at time xr[i]
  49. 		ve.push_back({a.first, 2, a.first});
  50. 	}
  51. 	for(auto a : mpl) {
  52. 		//xl[i] = a.first, xr[i] = a.second
  53. 		//query this segment which extends to xr[i] at time xl[i]
  54. 		ve.push_back({a.first, 3, a.second});
  55. 	}
  56. 	sort(ve.begin(), ve.end());
  57.  
  58. 	//sweep
  59. 	ll ans=0;
  60. 	//data structure to store the active right segments
  61. 	oset<int> s;
  62. 	for(event e : ve) {
  63. 		if(e.type==1) {
  64. 			//add segment
  65. 			s.insert(e.y);
  66. 		} else if(e.type==2) {
  67. 			//remove segment
  68. 			s.erase(e.y);
  69. 		} else {
  70. 			//left segment i intersects right segment j if xr[j] <= xr[i]
  71. 			//count right segments <= e.y
  72. 			ans+=s.order_of_key(e.y+1);
  73. 		}
  74. 	}
  75. 	cout << ans+1 << "\n";
  76. }
  77.  
  78. int main() {
  79. 	ios::sync_with_stdio(0);
  80. 	cin.tie(0);
  81.  
  82. 	int t;
  83. 	cin >> t;
  84. 	while(t--)
  85. 		solve();
  86. }
Success #stdin #stdout 0.01s 5488KB
comments (?)
stdin
copy 
1
1
100 200
150 350
-100 100
-100 60
stdout
copy 
2
https://ideone.com/QOPn0j
language:
C++14 (gcc 8.3)
created:
2 years 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!