fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAXN = (int)1e5 + 10;
  6.  
  7. int ST[MAXN << 2];
  8.  
  9. void down_lazy(int p, int l, int r)
  10. {
  11. 	ST[l] += ST[p];
  12. 	ST[r] += ST[p];
  13. 	ST[p] = 0;
  14. }
  15.  
  16. void update(int p, int b, int e, int x, int t)
  17. {
  18. 	if (b == e){
  19. 		ST[p] += t;
  20. 	}
  21. 	else{
  22. 		int mid = (b + e) >> 1;
  23. 		int left = p << 1;
  24. 		int right = left | 1;
  25.  
  26. 		if (ST[p]) down_lazy(p, left, right);
  27. 		if (x <= mid) ST[right] += t, update(left, b, mid, x, t);
  28. 		else update(right, mid + 1, e, x, t);
  29. 	}
  30. }
  31.  
  32. int query(int p, int b, int e, int x){
  33. 	if (b == e){
  34. 		return ST[p];
  35. 	}
  36. 	else{
  37. 		int mid = (b + e) >> 1;
  38. 		int left = p << 1;
  39. 		int right = left | 1;
  40.  
  41. 		if (ST[p]) down_lazy(p, left, right);
  42. 		if (x <= mid) return query(left, b, mid, x);
  43. 		else return query(right, mid + 1, e, x);
  44. 	}
  45. }
  46.  
  47. struct coder
  48. {
  49. 	int a, b, c;
  50. 	const bool operator <(const coder &other) const
  51. 	{
  52. 		if (a == other.a) return b < other.b;
  53. 		return a < other.a;
  54. 	}
  55. } L[(int)3e5 + 10];
  56.  
  57. int ANS[(int)3e5 + 10];
  58.  
  59. int main()
  60. {
  61. 	int n;
  62. 	scanf("%d", &n);
  63.  
  64. 	for (int i = 0; i < n; ++i){
  65. 		scanf("%d%d", &L[i].a, &L[i].b);
  66. 		L[i].c = i;
  67. 	}
  68.  
  69. 	sort(L, L + n);
  70. 	for (int i = 0, t; i < n; ){
  71. 		coder cur = L[i];
  72. 		for (t = 0 ; i < n && L[i].a == cur.a && L[i].b == cur.b; ++i, ++t)
  73. 			ANS[ L[i].c ] = query(1, 0, MAXN, L[i].b );
  74. 		update(1, 0, MAXN, cur.b, t);
  75. 	}
  76.  
  77. 	for (int i = 0; i < n; ++i) printf("%d\n", ANS[i]);
  78. }
  79.  
Success #stdin #stdout 0s 9600KB
comments (?)
stdin
copy 
8
1798 1832
862 700
1075 1089
1568 1557
2575 1984
1033 950
1656 1649
1014 1473
stdout
copy 
6
0
2
4
7
1
5
1
https://ideone.com/KIpdI4
language:
C++ (gcc 8.3)
created:
11 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!