fork download
copy 
  1.     #include <bits/stdc++.h>
  2.     using namespace std;
  3.  
  4.     const int maxn = 1e5+10;
  5.     //no bug but runtime
  6.     int n, d[maxn], pos[maxn];
  7.     pair<int, int> x[maxn];
  8.     int ks(int a, int b, int c)
  9.     {
  10.         return max({a, b, c});
  11.     }
  12.     int main()
  13.     {
  14.         freopen("test.inp", "r", stdin);
  15.         freopen("test.out", "w", stdout);
  16.         int n, q;
  17.         cin>>n>>q;
  18.         for(int i = 0; i<n; i++)
  19.         {
  20.             cin>>d[i];
  21.         }
  22.         for(int i = 1; i <= n; i++)
  23.         {
  24.             x[i] = make_pair(d[i] ,i);
  25.         }
  26.         sort(d+1, d+n+1);
  27.         sort(x+1, x+n+1);
  28.         for(int i = 0; i<n; i++)
  29.         {
  30.             int vt = x[i].second;
  31.             pos[vt] = i;
  32.         }
  33.         //for(int c: pos) cout<<c<< " =) "<<endl;
  34.        // pair<int, int>
  35.         while(q--)
  36.         {
  37.             ///30%, 40%(bf)
  38.             int u, v;
  39.             cin>>u>>v;
  40.              u = pos[u];
  41.              v = pos[v]; /// lấy được vị trí ở mảng đã sắp xếp
  42.             //y--;
  43.  
  44.             //int a = d[x];
  45.             //int b = d[y];
  46.             //find a, b
  47.  
  48.             long long l = min(x[u].first, x[v].first);
  49.             long long r = max(x[u].first, x[v].first);
  50.  
  51.             long long mid = (l + r) / 2;
  52.  
  53.             int p = lower_bound(d+1,d+n+1, mid) - d;
  54.             long long res = +1e6;
  55.             // (d[p-1], l, r)
  56.             res = max(abs(r-  d[p-1]), abs(l - d[p-1]));
  57.  
  58.             res = max(abs(r-  d[p]), abs(l - d[p]));
  59.  
  60.             res = max(abs(r-  d[p+1]), abs(l - d[p+1]));
  61.             // (d[p], l, r)
  62.  
  63.  
  64.             // (d[p+1], l, r)
  65.             //int b = ks(d[p - 1], l, r);
  66.            // int c = ks(d[p], l, r);
  67.             //int B = ks(d[p+1], l , r);
  68.             cout<<res<<"\n";
  69.  
  70.         }
  71.  
  72.         //return 0;
  73.     }
  74.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/EmdUOD
language:
C++ (gcc 8.3)
created:
2 days 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!