fork download
copy 
  1. ///****In the name of ALLAH, most Gracious, most Compassionate****//
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7. typedef pair <int, int> pii;
  8.  
  9. #define ALL(a) a.begin(), a.end()
  10. #define FastIO ios::sync_with_stdio(false); cin.tie(0);cout.tie(0)
  11. #define IN freopen("input.txt","r+",stdin)
  12. #define OUT freopen("output.txt","w+",stdout)
  13.  
  14. #define DBG(a) cerr<< "line "<<__LINE__ <<" : "<< #a <<" --> "<<(a)<<endl
  15. #define NL cerr<<endl
  16.  
  17. template < class T1,class T2>
  18. ostream &operator <<(ostream &os,const pair < T1,T2 > &p)
  19. {
  20.     os<<"{"<<p.first<<","<<p.second<<"}";
  21.     return os;
  22. }
  23.  
  24. const int N=3e5+5;
  25. const int oo=1e9+7;
  26.  
  27. int n;
  28. pii a[N];
  29.  
  30.  
  31. int32_t main()
  32. {
  33.     FastIO;
  34.     cin>>n;
  35. 	for(int i=0;i<n;i++)
  36. 		cin>>a[i].second>>a[i].first;
  37. 	sort(a,a+n);
  38. 	vector<int> vs;
  39. 	for(int i=0;i<n;i++)
  40. 	{
  41. 		vs.push_back(a[i].second);
  42. 	}
  43. 	sort(ALL(vs));
  44. 	vs.erase(unique(ALL(vs)),vs.end());
  45.  
  46. 	ll ans=0;
  47. 	for(int i=0;i<n;i++)
  48. 	{
  49. 		int j =i;
  50. 		while(j<n and a[i].first == a[j].first)
  51. 			j++;
  52. 		j--;
  53. 		// [i,j]
  54. 		// DBG(i);
  55. 		// DBG(j);
  56.  
  57. 		vector<ll> z;
  58. 		ll last = -1;
  59. 		for(int k=i;k<=j;k++)
  60. 		{
  61. 			int now = lower_bound(ALL(vs),a[k].second) - vs.begin();
  62. 			z.push_back(now - last-1);
  63. 			last = now;
  64. 		}
  65. 		z.push_back(((ll)vs.size()) - last - 1);
  66. 		// DBG(&z);
  67. 		// for(int k: z)
  68. 		// 	cerr<<k<<" ";
  69. 		// NL;
  70. 		last = z[0]+1;
  71. 		for(int k=1;k<z.size();k++)
  72. 		{
  73. 			ans+= (z[i]+1)*last;
  74. 			last+=z[k]+1;
  75. 		}
  76.  
  77. 		i=j;
  78. 	}
  79. 	cout<<ans<<"\n";
  80. }	
  81.  
Success #stdin #stdout 0.01s 5436KB
comments (?)
stdin
copy 
3
1 1
1 2
1 3
stdout
copy 
3
https://ideone.com/XWwpSD
language:
C++14 (gcc 8.3)
created:
1 year 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!