fork download
copy 
  1. /*input
  2. 3 3
  3. 1 7
  4. 10 5
  5. 8 9
  6. 3 0
  7. 3 1 1
  8. 6 2 1 2
  9. */
  10. #include <bits/stdc++.h>
  11. using namespace std;
  12. typedef long long ll;
  13. typedef long double ld;
  14. const ll INF = 2e18;
  15. const ld epss = 3e-11;
  16. struct line
  17. {
  18. 	ll c, a;
  19. 	int i;
  20. 	// c - ax
  21. 	ll y(ll x)
  22. 	{
  23. 		return c - a * x;
  24. 	}
  25. };
  26. ld R(line a, line b)
  27. {
  28. 	return ld(b.c - a.c) / ld(b.a - a.a);
  29. }
  30. int main()
  31. {
  32. 	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  33. 	int N, M;
  34. 	cin >> N >> M;
  35. 	line X[N];
  36. 	bool galim[N + 1];
  37. 	for (int i = 0; i < N; i++)
  38. 	{
  39. 		ll x, p;
  40. 		cin >> x >> p;
  41. 		X[i].c = p + x * x;
  42. 		X[i].a = 2 * x;
  43. 		X[i].i = i + 1;
  44. 		galim[i] = true;
  45. 	}
  46. 	sort(X, X + N, [](line a, line b) {return a.a < b.a;});
  47. 	int nr[N + 1];
  48. 	for (int i = 0; i < N; i++)
  49. 		nr[X[i].i] = i;
  50. 	vector<vector<int>>A;
  51. 	vector<int>B;
  52. 	int kiek = min(500, (int)(sqrt(N)) + 1);
  53. 	bool gal[N];
  54. 	fill_n(gal, N, true);
  55. 	while (kiek--)
  56. 	{
  57. 		vector<int>ids;
  58. 		vector<ld>r;
  59. 		for (int i = 0; i < N; i++)
  60. 		{
  61. 			if (!gal[i])
  62. 				continue;
  63. 			if (ids.empty())
  64. 			{
  65. 				ids = {i};
  66. 				continue;
  67. 			}
  68. 			while (!r.empty() && R(X[i], X[ids.back()]) <= r.back() + epss)
  69. 			{
  70. 				ids.pop_back();
  71. 				r.pop_back();
  72. 			}
  73. 			r.push_back(R(X[i], X[ids.back()]));
  74. 			ids.push_back(i);
  75. 		}
  76. 		if (ids.empty())
  77. 			break;
  78. 		A.push_back(ids);
  79. 		B.push_back(0);
  80. 		for (int i : ids)
  81. 			gal[i] = false;
  82. 	}
  83. 	pair<int, int>QUER[M];
  84. 	vector<int>DD[M];
  85. 	for (int i = 0; i < M; i++)
  86. 	{
  87. 		cin >> QUER[i].first;
  88. 		QUER[i].second = i;
  89. 		ll k;
  90. 		cin >> k;
  91. 		while (k--)
  92. 		{
  93. 			int c;
  94. 			cin >> c;
  95. 			c = nr[c];
  96. 			DD[i].push_back(c);
  97. 		}
  98. 	}
  99. 	sort(QUER, QUER + M);
  100. 	ll ats[M];
  101. 	for (int i = 0; i < M; i++)
  102. 	{
  103. 		ll x = QUER[i].first;
  104. 		for (int j : DD[QUER[i].second])
  105. 		{
  106. 			galim[j] = false;
  107. 		}
  108. 		ll ans = INF;
  109. 		if (DD[QUER[i].second].size() >= 500 || N * M <= 10000000)
  110. 		{
  111. 			for (int i = 0; i < N; i++)
  112. 			{
  113. 				if (galim[i])
  114. 				{
  115. 					ans = min(ans, X[i].y(x));
  116. 				}
  117. 			}
  118. 		}
  119. 		else
  120. 		{
  121. 			for (int a = 0; a < A.size(); a++)
  122. 			{
  123. 				while (B[a] + 1 < A[a].size())
  124. 				{
  125. 					if (X[A[a][B[a]]].y(x) >= X[A[a][B[a] + 1]].y(x))
  126. 						B[a]++;
  127. 					else
  128. 						break;
  129. 				}
  130. 				int i = B[a];
  131. 				if (galim[A[a][i]])
  132. 				{
  133. 					ans = min(ans, X[A[a][i]].y(x));
  134. 					break;
  135. 				}
  136. 				else
  137. 				{
  138. 					for (int c = i + 1; c < A[a].size(); c++)
  139. 					{
  140. 						if (galim[A[a][c]])
  141. 						{
  142. 							ans = min(ans, X[A[a][c]].y(x));
  143. 							break;
  144. 						}
  145. 					}
  146. 					for (int c = i - 1; c >= 0; c--)
  147. 					{
  148. 						if (galim[A[a][c]])
  149. 						{
  150. 							ans = min(ans, X[A[a][c]].y(x));
  151. 							break;
  152. 						}
  153. 					}
  154. 				}
  155. 			}
  156. 		}
  157. 		ats[QUER[i].second] = ans + x * x;
  158. 		for (int j : DD[QUER[i].second])
  159. 		{
  160. 			galim[j] = true;
  161. 		}
  162. 	}
  163. 	for (int i = 0; i < M; i++)
  164. 		cout << ats[i] << "\n";
  165. }
Runtime error #stdin #stdout 0.01s 4392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wY5eto
language:
C++14 (gcc 8.3)
created:
5 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!