fork download 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. using namespace std;
  5. template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
  6. template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
  7. const int MAXN = (1 << 20);
  8.  
  9. struct node
  10. {
  11. 	int64_t mn;
  12.  
  13. 	node() { mn = (int64_t)2e17; }
  14. 	node(int64_t val)
  15. 	{
  16. 		mn = val;
  17. 	}
  18. };
  19.  
  20. node temp, broken;
  21.  
  22. node merge(node l, node r)
  23. {
  24. 	temp.mn = min(l.mn, r.mn);
  25. 	return temp;
  26. }
  27.  
  28. struct segment_tree
  29. {
  30. 	node tr[4 * MAXN];
  31.  
  32. 	void init(int l, int r, int idx)
  33. 	{
  34. 		if(l == r)
  35. 		{
  36. 			tr[idx] = node();
  37. 			return;
  38. 		}
  39.  
  40. 		int mid = (l + r) >> 1;
  41. 		init(l, mid, 2 * idx + 1);
  42. 		init(mid + 1, r, 2 * idx + 2);
  43.  
  44. 		tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
  45. 	}
  46.  
  47. 	void update(int pos, int64_t val, int l, int r, int idx)
  48. 	{
  49. 		if(l > pos || r < pos)
  50. 			return;
  51.  
  52. 		if(l == r && l == pos)
  53. 		{
  54. 			chkmin(tr[idx].mn, val);
  55. 			return;
  56. 		}
  57.  
  58. 		int mid = (l + r) >> 1;
  59. 		update(pos, val, l, mid, 2 * idx + 1);
  60. 		update(pos, val, mid + 1, r, 2 * idx + 2);
  61.  
  62. 		tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
  63. 	}
  64.  
  65. 	node query(int qL, int qR, int l, int r, int idx)
  66. 	{
  67. 		if(l > qR || r < qL)
  68. 			return broken;
  69.  
  70. 		if(qL <= l && r <= qR)
  71. 			return tr[idx];
  72.  
  73. 		int mid = (l + r) >> 1;
  74. 		return merge(query(qL, qR, l, mid, 2 * idx + 1), query(qL, qR, mid + 1, r, 2 * idx + 2));
  75. 	}
  76. };
  77.  
  78. int n, m;
  79. vector<int64_t> sorted;
  80. int L[MAXN], R[MAXN], T[MAXN];
  81. int perm[MAXN];
  82. pair<int, int> que[MAXN];
  83.  
  84. void read()
  85. {
  86. 	cin >> n >> m;
  87. 	for(int i = 0; i < n; i++)
  88. 	{
  89. 		cin >> L[i] >> R[i] >> T[i];
  90. 		//if(L[i] > R[i]) swap(L[i], R[i]);
  91. 		sorted.push_back(L[i]);
  92. 		sorted.push_back(R[i]);
  93. 	}
  94.  
  95. 	for(int i = 0; i < m; i++)
  96. 	{
  97. 		cin >> que[i].first >> que[i].second;
  98. 		//if(que[i].first > que[i].second) swap(que[i].first, que[i].second);
  99. 		sorted.push_back(que[i].first);
  100. 		sorted.push_back(que[i].second);
  101. 	}	
  102. }
  103.  
  104. int64_t answer[MAXN];
  105.  
  106. int get(int x) { return lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin(); }
  107.  
  108. bool cmp_inside(pair<int, int> a, pair<int, int> b)
  109. {
  110. 	int r1, r2;
  111.  
  112. 	if(a.second) r1 = que[a.first].second;
  113. 	else r1 = R[a.first];
  114.  
  115. 	if(b.second) r2 = que[b.first].second;
  116. 	else r2 = R[b.first];
  117.  
  118. 	if(r1 != r2) return r1 < r2;
  119. 	return a.second < b.second;
  120. }
  121.  
  122. bool cmp_outside(pair<int, int> a, pair<int, int> b)
  123. {
  124. 	int r1, r2;
  125.  
  126. 	if(a.second) r1 = que[a.first].first;
  127. 	else r1 = L[a.first];
  128.  
  129. 	if(b.second) r2 = que[b.first].first;
  130. 	else r2 = L[b.first];
  131.  
  132. 	if(r1 != r2) return r1 < r2;
  133. 	return a.second < b.second;
  134. }
  135.  
  136. segment_tree t;
  137.  
  138. void solve_inside()
  139. {	
  140. 	vector<pair<int, int> > li;
  141. 	for(int i = 0; i < n; i++)
  142. 		if(L[i] <= R[i]) 
  143. 			li.push_back({i, 0});
  144.  
  145. 	for(int i = 0; i < m; i++)
  146. 		if(que[i].first <= que[i].second) 
  147. 			li.push_back({i, 1});
  148.  
  149. 	sort(li.begin(), li.end(), cmp_inside);
  150.  
  151. 	t.init(0, sorted.size(), 0);
  152.  
  153. 	for(auto it: li)
  154. 	{
  155. 		int type = it.second;
  156. 		if(type == 0)
  157. 			t.update(L[it.first], T[it.first] + sorted[L[it.first]] - sorted[R[it.first]], 0, sorted.size(), 0);
  158. 		else
  159. 			chkmin(answer[it.first], sorted[que[it.first].second] - sorted[que[it.first].first] + t.query(que[it.first].first, sorted.size(), 0, sorted.size(), 0).mn);
  160. 	}
  161. }
  162.  
  163. void solve_left()
  164. {	
  165. 	vector<pair<int, int> > li;
  166. 	for(int i = 0; i < n; i++)
  167. 		if(L[i] <= R[i]) 
  168. 			li.push_back({i, 0});
  169.  
  170. 	for(int i = 0; i < m; i++)
  171. 		if(que[i].first <= que[i].second) 
  172. 			li.push_back({i, 1});
  173.  
  174. 	sort(li.begin(), li.end(), cmp_outside);
  175.  
  176. 	t.init(0, sorted.size(), 0);
  177.  
  178. 	for(auto it: li)
  179. 	{
  180. 		int type = it.second;
  181. 		if(type == 0)
  182. 			t.update(R[it.first], T[it.first] - sorted[L[it.first]] - sorted[R[it.first]], 0, sorted.size(), 0);
  183. 		else 
  184. 			chkmin(answer[it.first], sorted[que[it.first].second] + sorted[que[it.first].first] + t.query(que[it.first].first, que[it.first].second, 0, sorted.size(), 0).mn);
  185. 	}
  186. }
  187.  
  188. void solve_outside()
  189. {	
  190. 	vector<pair<int, int> > li;
  191. 	for(int i = 0; i < n; i++)
  192. 		if(L[i] <= R[i]) 
  193. 			li.push_back({i, 0});
  194.  
  195. 	for(int i = 0; i < m; i++)
  196. 		if(que[i].first <= que[i].second) 
  197. 			li.push_back({i, 1});
  198.  
  199. 	sort(li.begin(), li.end(), cmp_outside);
  200.  
  201. 	t.init(0, sorted.size(), 0);
  202.  
  203. 	for(auto it: li)
  204. 	{
  205. 		int type = it.second;
  206. 		if(type == 0)
  207. 			t.update(R[it.first], T[it.first] - sorted[L[it.first]] + sorted[R[it.first]], 0, sorted.size(), 0);
  208. 		else 
  209. 			chkmin(answer[it.first], -sorted[que[it.first].second] + sorted[que[it.first].first] + t.query(que[it.first].second, sorted.size(), 0, sorted.size(), 0).mn);
  210. 	}
  211. }
  212.  
  213. void solve_right()
  214. {	
  215. 	vector<pair<int, int> > li;
  216. 	for(int i = 0; i < n; i++)
  217. 		if(L[i] <= R[i]) 
  218. 			li.push_back({i, 0});
  219.  
  220. 	for(int i = 0; i < m; i++)
  221. 		if(que[i].first <= que[i].second) 
  222. 			li.push_back({i, 1});
  223.  
  224. 	sort(li.begin(), li.end(), cmp_inside);
  225. 	reverse(li.begin(), li.end());
  226.  
  227. 	t.init(0, sorted.size(), 0);
  228.  
  229. 	for(auto it: li)
  230. 	{
  231. 		int type = it.second;
  232. 		if(type == 0)
  233. 			t.update(L[it.first], T[it.first] + sorted[L[it.first]] + sorted[R[it.first]], 0, sorted.size(), 0);
  234. 		else 
  235. 			chkmin(answer[it.first], -sorted[que[it.first].second] - sorted[que[it.first].first] + t.query(que[it.first].first, que[it.first].second, 0, sorted.size(), 0).mn);
  236. 	}
  237. }
  238.  
  239. void solve()
  240. {
  241. 	for(int i = 0; i < m; i++)
  242. 		answer[i] = abs(que[i].first - que[i].second);
  243.  
  244. 	sort(sorted.begin(), sorted.end());
  245. 	sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
  246.  
  247. 	for(int i = 0; i < m; i++)
  248. 	{
  249. 		que[i].first = get(que[i].first);
  250. 		que[i].second = get(que[i].second);
  251. 	}
  252.  
  253. 	for(int i = 0; i < n; i++)
  254. 		L[i] = get(L[i]), R[i] = get(R[i]);
  255.  
  256. 	solve_inside();
  257. 	solve_left();
  258. 	solve_outside();
  259. 	solve_right();
  260.  
  261. 	for(int i = 0; i < m; i++)
  262. 	{
  263. 		que[i].first = -sorted[que[i].first];
  264. 		que[i].second = -sorted[que[i].second];
  265. 	}
  266.  
  267. 	for(int i = 0; i < n; i++)
  268. 		L[i] = -sorted[L[i]], R[i] = -sorted[R[i]];
  269.  
  270. 	for(auto &it: sorted) it *= -1;
  271. 	sort(sorted.begin(), sorted.end());
  272.  
  273. 	for(int i = 0; i < m; i++)
  274. 	{
  275. 		que[i].first = get(que[i].first);
  276. 		que[i].second = get(que[i].second);
  277. 	}
  278.  
  279. 	for(int i = 0; i < n; i++)
  280. 		L[i] = get(L[i]), R[i] = get(R[i]);
  281.  
  282.  
  283. 	solve_inside();
  284. 	solve_left();
  285. 	solve_outside();
  286. 	solve_right();
  287.  
  288. 	for(int i = 0; i < m; i++)
  289. 		cout << answer[i] << endl;
  290. }
  291.  
  292. int main()
  293. {
  294. 	freopen("slingshot.in", "r", stdin);
  295. 	freopen("slingshot.out", "w", stdout);
  296. 	ios_base::sync_with_stdio(false);
  297. 	cin.tie(NULL);
  298.  
  299. 	read();
  300. 	solve();
  301. 	return 0;
  302. }
  303.  
  304.  
Runtime error #stdin #stdout #stderr 0.02s 36032KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
terminate called after throwing an instance of 'std::ios_base::failure[abi:cxx11]'
  what():  basic_filebuf::underflow error reading the file: iostream error
https://ideone.com/xlpNy6
language:
C++14 (gcc 8.3)
created:
6 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!