fork(1) download
copy 
  1. /* 
  2.    Copyright 2013 Jakub "Cubix651" Cisło
  3.    Interval tree (interval - interval): (+, max)
  4.    Add value for interval and ask about maximum value of interval
  5.    Complexity: O(z log n)
  6. */
  7.  
  8. #include <cstdio>
  9. #include <algorithm>
  10. using namespace std;
  11.  
  12. const int MAX = 131074;
  13. int n, m, z, p, k, l, W[MAX], M[MAX], S;
  14.  
  15. int greaterPow2(int x)
  16. {
  17. 	int res = 1;
  18. 	while(res < x)
  19. 		res <<= 1;
  20. 	return res;
  21. }
  22.  
  23. void insert(int a, int b, int c)
  24. {
  25. 	a += S;
  26. 	b += S;
  27.  
  28. 	W[a] += c;
  29. 	M[a] += c;
  30. 	if(a != b)
  31. 	{
  32. 		W[b] += c;
  33. 		M[b] += c;
  34. 	}
  35.  
  36. 	while(a>>1 != b>>1)
  37. 	{
  38. 		if(!(a&1))
  39. 		{
  40. 			W[a+1] += c;
  41. 			M[a+1] += c;
  42. 		}
  43. 		if(b&1)
  44. 		{
  45. 			W[b-1] += c;
  46. 			M[b-1] += c;
  47. 		}
  48.  
  49. 		a>>=1;
  50. 		b>>=1;
  51.  
  52. 		M[a] = max(M[a<<1], M[(a<<1)+1]) + W[a];
  53. 		M[b] = max(M[b<<1], M[(b<<1)+1]) + W[b];
  54. 	}
  55. 	while(a != 1)
  56. 	{
  57. 		a>>=1;
  58. 		M[a] = max(M[a<<1], M[(a<<1)+1]) + W[a];
  59. 	}
  60. }
  61.  
  62. int x, y;
  63.  
  64. int _query(int a, int b, int v, int sum)
  65. {
  66. 	if(x <= a && b <= y)
  67. 		return sum + M[v];
  68. 	if(x > b || y < a)
  69. 		return 0;
  70. 	return max(
  71. 		_query(a, (a+b)/2, 2*v, sum+W[v]),
  72. 		_query((a+b)/2 + 1, b, 2*v+1, sum+W[v])
  73. 		);
  74. }
  75.  
  76. int query(int a, int b)
  77. {
  78. 	x = a;
  79. 	y = b;
  80. 	return _query(0, S-1, 1, 0);
  81. }
  82.  
  83. void printTree()
  84. {
  85. 	for(int i = 1; i <= 2*S; ++i)
  86. 		printf("(%d %d) ", W[i], M[i]);
  87. 	printf("\n\n");
  88. }
  89.  
  90. /* Example: Task "Rails" (IX OI) */
  91. int main()
  92. {
  93. 	scanf("%d%d%d", &n, &m, &z);
  94. 	S = greaterPow2(n-1);
  95. 	while(z--)
  96. 	{
  97. 		scanf("%d%d%d", &p, &k, &l);
  98. 		--k;
  99. 		//printTree();
  100. 		if(query(--p, --k) + l <= m)
  101. 		{
  102. 			insert(p, k, l);
  103. 			printf("T\n");
  104. 		}
  105. 		else
  106. 		{
  107. 			printf("N\n");
  108. 		}
  109. 	}
  110. 	return 0;
  111. }
Success #stdin #stdout 0s 3880KB
comments (?)
stdin
copy 
4 6 4
1 4 2
1 3 2
2 4 3
1 2 3
stdout
copy 
T
T
N
N
https://ideone.com/TbG9aA
Interval tree
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!