fork download
copy 
  1. #include <bits/stdc++.h>
  2. /* MACROS */
  3.  
  4. #define  all(A)			(A).begin() , (A).end()
  5. #define  rall(A)		(A).rbegin() , (A).rend()
  6. #define  sz(A)			(int)(A).size()
  7. #define  pb				push_back
  8. #define  ppb			pop_back
  9. #define  mp				make_pair
  10. #define  ln(X)			(int)(X).length()
  11. #define  square(X)		((X)*(X))
  12. #define  cube(X)		((X)*(X)*(X))
  13. #define  y1				thisisnotnonsenseasyoumaythink
  14. #define  forn(i, n)		for (int i = 0; i < int(n); i++)
  15. #define  forr(i, n)		for (int i = int(n - 1); i >= 0; i--)
  16. #define  fora(i, a, b)  for (int i = int(a); i <= int(b); i++)
  17. #define  forb(i, a, b)  for (int i = int(a); i >= int(b); i--)
  18. #define  fore(it, a)	for(__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
  19. #define  dbg(vari)		cerr << #vari << " = " << (vari) << endl
  20. #define  dbg2(vari)		cerr << #vari << " = " << (vari) << ", "
  21. #define  prt(vari)		cerr << (vari) << endl
  22. #define  prt2(vari)		cerr << (vari) << ", "
  23.  
  24. using namespace std;
  25.  
  26. /* TYPE DEFINITIONS */
  27. typedef		long long		i64;
  28. typedef		vector<int>		vi;
  29. typedef		pair<int,int>	pi;
  30.  
  31. /* TOOLS */
  32. template <class T> void debug(T a,T b){ for (; a != b; a++) cerr << *a << ' '; cerr << endl; }
  33.  
  34. #define ID second
  35. #define SCR1 first.first
  36. #define SCR2 first.second
  37.  
  38. int n;
  39. pair<pi, int> scr[500010];
  40. int hiest[500010];
  41. int loest[500010];
  42.  
  43. struct fenwick {
  44. 	int cum[710];
  45.  
  46. 	fenwick() {
  47. 		fill(cum, cum+710, 0);
  48. 	}
  49.  
  50. 	void add(int idx, int val) {
  51. 		for (; idx <= 700; idx = (idx|(idx+1)))
  52. 			cum[idx] += val;
  53. 	}
  54.  
  55. 	int get(int idx) {
  56. 		int ret = 0;
  57. 		for (; idx >= 0; idx = (idx&(idx+1))-1)
  58. 			ret += cum[idx];
  59. 		return ret;
  60. 	}
  61. };
  62.  
  63. fenwick f1;
  64. fenwick f2;
  65. fenwick f3;
  66. fenwick f4;
  67.  
  68. int main()
  69. {
  70.     //freopen("test.in", "r", stdin);
  71.     //freopen("test.out", "w", stdout);
  72. 	cin >> n;
  73.  
  74. 	for (int i = 0; i < n; i++) {
  75. 		cin >> scr[i].SCR1;
  76. 		cin >> scr[i].SCR2;
  77. 		scr[i].SCR1 += 2;
  78. 		scr[i].SCR2 += 2;
  79. 		scr[i].ID = i;
  80. 	}
  81.  
  82. 	sort(scr, scr+n);
  83.  
  84. 	for (int i = n-1; i >= 0;) {
  85. 		int j = i;
  86.  
  87. 		while (j >= 0 && scr[i].SCR1 == scr[j].SCR1) {
  88. 			hiest[ scr[j].ID ] = 1;
  89. 			hiest[ scr[j].ID ] += f1.get(700) - f1.get(scr[j].SCR2);
  90. 			j--;
  91. 		}
  92.  
  93. 		for (int k = j+1; k <= i; k++)
  94. 			f1.add(scr[k].SCR2, 1);
  95.  
  96. 		i = j;
  97. 	}
  98.  
  99. 	for (int i = 0; i < n; i++) {
  100. 		if (scr[i].SCR1 == 2)
  101. 			f3.add(scr[i].SCR2, 1);
  102.  
  103. 		if (scr[i].SCR2 == 2)
  104. 			f4.add(scr[i].SCR1, 1);
  105. 	}
  106.  
  107. 	for (int i = 0; i < n;) {
  108. 		int j = i;
  109.  
  110. 		while (j < n && scr[i].SCR1 == scr[j].SCR1) {
  111. 			loest[ scr[j].ID ] = n;
  112. 			loest[ scr[j].ID ] -= f2.get(scr[j].SCR2-1);
  113.  
  114. 			if (scr[j].SCR1 == 652)
  115. 				loest[ scr[j].ID ] -= (f3.get(scr[j].SCR2) - f3.get(scr[j].SCR2-1));
  116.  
  117. 			if (scr[j].SCR2 == 652)
  118. 				loest[ scr[j].ID ] -= (f4.get(scr[j].SCR1) - f4.get(scr[j].SCR1-1));
  119.  
  120. 			j++;
  121. 		}
  122.  
  123. 		for (int k = i; k < j; k++)
  124. 			f2.add(scr[k].SCR2, 1);
  125.  
  126. 		i = j;
  127. 	}
  128.  
  129. 	for (int i = 0; i < n; i++) {
  130. 		cout << hiest[i] << " ";
  131. 		cout << loest[i] << "\n";
  132. 	}
  133.  
  134. 	return EXIT_SUCCESS;
  135. }
  136.  
Success #stdin #stdout 0s 13080KB
comments (?)
stdin
copy 
10
650 550
550 554
560 512
610 460
610 456
650 392
580 436
650 366
520 456
490 456
stdout
copy 
1 4
1 8
2 8
2 7
2 9
1 10
4 10
1 10
5 10
5 10
https://ideone.com/hlnoGb
language:
C++ (gcc 8.3)
created:
9 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!