Guest User

Untitled

a guest
Mar 1st, 2018
143
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. using namespace std;
  5.  
  6. const int N = 100007;
  7. const int TREE_SIZE = 5000007;
  8. const long long INF = (long long)(1e9) * 1ll * (long long)(1e5) + 7;
  9. const int TO = (1e9);
  10.  
  11. struct slingshot {
  12.     int x,y,t;
  13.     slingshot(){}
  14.     slingshot(int a, int b, int c): x(a), y(b), t(c) {}
  15.     bool operator <(const slingshot &a) const {
  16.         return x<a.x;
  17.     }
  18. };
  19.  
  20. struct query {
  21.     int x,y,idx;
  22.     query(){}
  23.     query(int a, int b, int c): x(a), y(b), idx(c) {}
  24.     bool operator <(const query &a) const {
  25.         return x<a.x;
  26.     }
  27. };
  28.  
  29. struct segment_tree {
  30.     int nodes_count;
  31.     int left[TREE_SIZE],right[TREE_SIZE];
  32.     long long tree[TREE_SIZE];
  33.  
  34.     segment_tree() {
  35.         nodes_count=1;
  36.         memset(left,0,sizeof(left));
  37.         memset(right,0,sizeof(right));
  38.         fill(tree,tree+TREE_SIZE,INF);
  39.     }
  40.  
  41.     void clear() {
  42.         for(int i=1;i<=nodes_count;i++) {
  43.             left[i]=right[i]=0;
  44.             tree[i]=INF;
  45.         }
  46.         nodes_count=1;
  47.     }
  48.  
  49.     void extend_left(int node) {
  50.         if(left[node]==0) {
  51.             left[node]=++nodes_count;
  52.         }
  53.     }
  54.  
  55.     void extend_right(int node) {
  56.         if(right[node]==0) {
  57.             right[node]=++nodes_count;
  58.         }
  59.     }
  60.  
  61.     void update(int a, int b, int pos, int node, long long value) {
  62.         if(a==b) {
  63.             tree[node]=min(tree[node],value);
  64.             return;
  65.         }
  66.         if(pos<=((a+b)>>1)) {
  67.             extend_left(node);
  68.             update(a,(a+b)>>1,pos,left[node],value);
  69.             tree[node]=min(tree[node],tree[left[node]]);
  70.         }
  71.         else {
  72.             extend_right(node);
  73.             update(((a+b)>>1)+1,b,pos,right[node],value);
  74.             tree[node]=min(tree[node],tree[right[node]]);
  75.         }
  76.     }
  77.  
  78.     void update(int pos, int value) {
  79.         update(0,TO,pos,1,value);
  80.     }
  81.  
  82.     long long query(int a, int b, int i, int j, int node) {
  83.         if(a>b || a>j || b<i) return INF;
  84.         if(a>=i && b<=j) return tree[node];
  85.         extend_left(node);
  86.         extend_right(node);
  87.         return min(query(a,(a+b)>>1,i,j,left[node]),query(((a+b)>>1)+1,b,i,j,right[node]));
  88.     }
  89.  
  90.     long long query(int a, int b) {
  91.         return query(0,TO,a,b,1);
  92.     }
  93. };
  94.  
  95. int n,m;
  96. vector < slingshot > a1,a2;
  97. vector < query > q1,q2;
  98. segment_tree st;
  99. int answer[N];
  100.  
  101. void solve(vector < slingshot > shots, vector < query > queries) {
  102.     int i,pos;
  103.  
  104.     sort(shots.begin(),shots.end());
  105.     sort(queries.begin(),queries.end());
  106.    
  107.     /*
  108.         First case: x, xi, yi, y
  109.         Minimize: y-x+xi+ti-yi   <=>   Minimize: xi+ti-yi
  110.     */
  111.     st.clear();
  112.     pos=(int)(shots.size())-1;
  113.     for(i=(int)(queries.size())-1;i>=0;i--) {
  114.         //Add all relevant shots
  115.         while(pos>=0 && shots[pos].x>=queries[i].x) {
  116.             st.update(shots[pos].y,0ll+shots[pos].x+shots[pos].t-shots[pos].y);
  117.             --pos;
  118.         }
  119.  
  120.         answer[queries[i].idx]=min(0ll+answer[queries[i].idx],queries[i].y-queries[i].x+st.query(queries[i].x,queries[i].y));
  121.     }
  122.  
  123.     /*
  124.         Second case: x, xi, y, yi
  125.         Minimize: xi-x+ti+yi-y  <=>  Minimize: -x-y+xi+yi+ti  <=>  Minize: xi+yi+ti
  126.     */
  127.     st.clear();
  128.     pos=(int)(shots.size())-1;
  129.     for(i=(int)(queries.size())-1;i>=0;i--) {
  130.         //Add all relevant shots
  131.         while(pos>=0 && shots[pos].x>=queries[i].x) {
  132.             st.update(shots[pos].y,0ll+shots[pos].x+shots[pos].y+shots[pos].t);
  133.             --pos;
  134.         }
  135.  
  136.         answer[queries[i].idx]=min(0ll+answer[queries[i].idx],-queries[i].x-queries[i].y+st.query(queries[i].y,TO));
  137.     }
  138.  
  139.     /*
  140.         Third case: xi, x, yi, y
  141.         Minimize: x-xi+ti+y-yi  <=>  Minimize: x+y+ti-xi-yi  <=>  Minimize:  ti-xi-yi
  142.     */
  143.     st.clear();
  144.     pos=0;
  145.     for(i=0;i<(int)(queries.size());i++) {
  146.         //Add all relevant shots
  147.         while(pos<(int)(shots.size()) && shots[pos].x<=queries[i].x) {
  148.             st.update(shots[pos].y,0ll+shots[pos].t-shots[pos].x-shots[pos].y);
  149.             ++pos;
  150.         }
  151.  
  152.         answer[queries[i].idx]=min(0ll+answer[queries[i].idx],queries[i].x+queries[i].y+st.query(queries[i].x,queries[i].y));
  153.     }
  154.  
  155.     /*
  156.         Fourth case: xi, x, y, yi
  157.         Minimize: x-xi+ti+yi-y  <=>  Minimize: x-y+ti+yi-xi  <=>  Minimize: ti+yi-xi
  158.     */
  159.     st.clear();
  160.     pos=0;
  161.     for(i=0;i<(int)(queries.size());i++) {
  162.         //Add all relevant shots
  163.         while(pos<(int)(shots.size()) && shots[pos].x<=queries[i].x) {
  164.             st.update(shots[pos].y,0ll+shots[pos].t+shots[pos].y-shots[pos].x);
  165.             ++pos;
  166.         }
  167.  
  168.         answer[queries[i].idx]=min(0ll+answer[queries[i].idx],queries[i].x-queries[i].y+st.query(queries[i].y,TO));
  169.     }
  170. }
  171.  
  172. int main() {
  173.     ios_base::sync_with_stdio(false);
  174.     cin.tie(NULL);
  175.     freopen("slingshot.in","r",stdin);
  176.     freopen("slingshot.out","w",stdout);
  177.     int i,x,y,z;
  178.  
  179.     scanf("%d %d", &n, &m);
  180.     for(i=1;i<=n;i++) {
  181.         scanf("%d %d %d", &x, &y, &z);
  182.         if(x<=y) {
  183.             a1.push_back(slingshot(x,y,z));
  184.         }
  185.         else {
  186.             a2.push_back(slingshot(y,x,z));
  187.         }
  188.     }
  189.     for(i=1;i<=m;i++) {
  190.         scanf("%d %d", &x, &y);
  191.         answer[i]=abs(x-y);
  192.         if(x<=y) {
  193.             q1.push_back(query(x,y,i));
  194.         }
  195.         else {
  196.             q2.push_back(query(y,x,i));
  197.         }
  198.     }
  199.  
  200.     solve(a1,q1);
  201.     solve(a2,q2);
  202.  
  203.     for(i=1;i<=m;i++) {
  204.         printf("%d\n", answer[i]);
  205.     }
  206.    
  207.     return 0;
  208. }
RAW Paste Data