Guest User

Untitled

a guest
Feb 28th, 2018
201
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m;
  4. map<int,int>cm;
  5. const int mxn = (1e5) + 5;
  6.  
  7. struct shot{
  8. int x,y,t;
  9. };
  10. bool cmp(shot a, shot b){
  11. if(a.x == b.x)return a.y < b.y;
  12. return a.x < b.x;
  13. }
  14. vector<shot>v;
  15. vector<shot>vv;
  16.  
  17. struct qu{
  18. int x,y,i;
  19. };
  20. bool cmp1(qu a, qu b){
  21. if(a.x == b.x)return a.y < b.y;
  22. return a.x < b.x;
  23. }
  24. vector<qu>Q;
  25. vector<qu>QQ;
  26.  
  27.  
  28. struct segtree{
  29. long long st[mxn * 4];
  30. multiset<long long>mn[mxn * 4];
  31. void clear(){
  32. for(int i = 0 ; i < mxn * 4 ; ++i)
  33. {
  34. mn[i].clear();
  35. st[i] = (1LL << 60);
  36. }
  37. }
  38. void update(int p,int l,int r,int i,long long x, bool q)
  39. {
  40. if(l == r)
  41. {
  42. if(q)mn[p].insert(x);
  43. else mn[p].erase(mn[p].find(x));
  44.  
  45. if(mn[p].empty())st[p] = (1LL << 60);
  46. else st[p] = *mn[p].begin();
  47.  
  48. return;
  49. }
  50. int md = (l + r) / 2;
  51. if(i <= md)update(p * 2, l, md, i, x, q);
  52. else update(p * 2 + 1, md + 1, r, i, x, q);
  53. st[p] = min(st[p * 2], st[p * 2 + 1]);
  54. }
  55. long long rmq(int p,int l,int r,int i,int j)
  56. {
  57. if(r < i || l > j)return (1LL << 60);
  58. if(l >= i && r <= j)return st[p];
  59. int md = (l + r) / 2;
  60. long long x = rmq(p * 2, l, md, i, j);
  61. long long y = rmq(p * 2 + 1, md + 1, r, i, j);
  62. return min(x, y);
  63. }
  64. };
  65. segtree st1, st2, st3, st4;
  66.  
  67. int ans[mxn];
  68. void proc()
  69. {
  70. sort(v.begin(), v.end(), cmp);
  71. sort(Q.begin(), Q.end(), cmp1);
  72. int it = 0;
  73.  
  74. st1.clear();
  75. st2.clear();
  76. st3.clear();
  77. st4.clear();
  78.  
  79. for(int i = 0 ; i < v.size() ; ++i)
  80. {
  81. int x = v[i].x;
  82. int y = v[i].y;
  83. int t = v[i].t;
  84. int cmy = cm[y];
  85. st3.update(1, 1, n, cmy, x - y + t, 1);
  86. st4.update(1, 1, n, cmy, x + y + t, 1);
  87. }
  88.  
  89. for(int i = 0 ; i < Q.size() ; ++i)
  90. {
  91. int x = Q[i].x;
  92. int y = Q[i].y;
  93. int j = Q[i].i;
  94. int answer = Q[i].y - Q[i].x;
  95. while(it < v.size() && v[it].x <= x)
  96. {
  97.  
  98. int xx = v[it].x;
  99. int yy = v[it].y;
  100. int t = v[it].t;
  101. ++it;
  102.  
  103. int cmy = cm[yy];
  104.  
  105. st3.update(1, 1, n, cmy, xx - yy + t, 0);
  106. st4.update(1, 1, n, cmy, xx + yy + t, 0);
  107. st1.update(1, 1, n, cmy, - xx - yy + t, 1);
  108. st2.update(1, 1, n, cmy, - xx + yy + t, 1);
  109. }
  110. map<int,int>::iterator itr = cm.lower_bound(y);
  111.  
  112. if(itr != cm.end())
  113. {
  114. int in = itr->second;
  115. long long vl;
  116.  
  117. vl = st2.rmq(1, 1, n, in, n) + x - y;
  118. if(vl < answer)answer = vl;
  119.  
  120. vl = st4.rmq(1, 1, n, in, n) - x - y;
  121. if(vl < answer)answer = vl;
  122. }
  123. if(itr != cm.begin())
  124. {
  125. --itr;
  126. int in = itr->second;
  127. long long vl;
  128. vl = st1.rmq(1, 1, n, 1, in) + x + y;
  129. if(vl < answer)answer = vl;
  130.  
  131. vl = st3.rmq(1, 1, n, 1, in) - x + y;
  132. if(vl < answer)answer = vl;
  133. }
  134. ans[j] = answer;
  135. }
  136. }
  137. int main()
  138. {
  139. freopen("slingshot.in","r",stdin);
  140. freopen("slingshot.out","w",stdout);
  141. scanf("%d%d",&n,&m);
  142. for(int i = 0 ; i < n ; ++i)
  143. {
  144. shot s;
  145. cin>>s.x>>s.y>>s.t;
  146.  
  147. if(s.x < s.y)v.push_back(s);
  148. else
  149. {
  150. swap(s.x, s.y);
  151. vv.push_back(s);
  152. }
  153. cm[s.y] = 0;
  154. }
  155. for(int i = 0 ; i < m ; ++i)
  156. {
  157. qu q;
  158. q.i = i;
  159. cin>>q.x>>q.y;
  160.  
  161. if(q.x < q.y)Q.push_back(q);
  162. else
  163. {
  164. swap(q.x, q.y);
  165. QQ.push_back(q);
  166. }
  167. }
  168.  
  169. map<int,int>::iterator it = cm.begin();
  170. int in = 0;
  171. for(it ; it != cm.end() ; ++it)
  172. it->second = ++in;
  173.  
  174. proc();
  175. v = vv;
  176. Q = QQ;
  177.  
  178. proc();
  179. for(int i = 0 ; i < m ; ++i)
  180. printf("%d\n", ans[i]);
  181. return 0;
  182. }
RAW Paste Data