fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #pragma GCC optimize("Ofast,unroll-loops")
  4. #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  5. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  6.  
  7. #define int long long
  8. #define pii pair<int , int>
  9. #define FOR(i , a , b) for(int i = (a);i <= (b);i++)
  10. #define FOD(i , a , b) for(int i = (a);i >= (b);i--)
  11. #define REP(i , n) for(int i = 1;i <= (n);i++)
  12. #define REP0(i , n) for(int i = 0;i < (n);i++)
  13. #define pb push_back
  14. #define printclock cerr<<"\nTime : "<<1000*(double)clock()/(double)CLOCKS_PER_SEC<<"ms\n";
  15. const int mod = 1e9 + 7,inf = 1e18;
  16. const int mxn = 2e5 + 5;
  17. int bsize;
  18. int n, a[mxn];
  19. int chia[mxn];
  20. multiset<pii> ms;
  21. multiset<pair<int, pii> > diff;
  22. set<int> adj[mxn];
  23. int deg[mxn];
  24. int q, answer[mxn];
  25. int moleft = 0, moright = 0;
  26.  
  27. struct query
  28. {
  29.     int id, l, r;
  30. } arr[mxn];
  31.  
  32. bool cmp(query a, query b)
  33. {
  34.     if(chia[a.l] != chia[b.l]) return a.l < b.l;
  35.     else return a.r < b.r;
  36. }
  37.  
  38.  
  39.  
  40.  
  41.  
  42. void add(int x)
  43. {
  44.     if(moleft > moright) return;
  45.     if(ms.empty())
  46.     {
  47.         ms.insert({a[x], x});
  48.         return;
  49.     }
  50.     auto it = ms.lower_bound({a[x], -inf});
  51.     if(it != ms.begin()) it--;
  52.     int minpos = 0, mindiff = inf;
  53.     for(int cnt = 0; cnt < 3 && it != ms.end(); cnt++, it++)
  54.     {
  55.         auto p = *it;
  56.         int pos = p.second, val = p.first;
  57.         if(abs(a[x] - val) < mindiff)
  58.         {
  59.             mindiff = abs(a[x] - val);
  60.             minpos = pos;
  61.         }
  62.     }
  63.     ms.insert({a[x], x});
  64.     adj[x].insert(minpos);
  65.     adj[minpos].insert(x);
  66.     int a = x, b = minpos;
  67.     if(a > b) swap(a, b);
  68.     diff.insert({mindiff, {a, b}});
  69. }
  70.  
  71. void del(int x)
  72. {
  73.     if(ms.find({a[x], x}) != ms.end()) ms.erase(ms.find({a[x], x}));
  74.     for(auto v : adj[x])
  75.     {
  76.         adj[v].erase(x);
  77.         int d = abs(a[x] - a[v]);
  78.         int aa = v, bb = x;
  79.         if(aa > bb) swap(aa, bb);
  80.         if(diff.find({d, {aa, bb}}) != diff.end()) diff.erase(diff.find({d, {aa, bb}}));
  81.         if(adj[v].empty())
  82.         {
  83.             if((int)ms.size() > 0)
  84.             {
  85.                 auto it = ms.lower_bound({a[v], -inf});
  86.                 if(it != ms.begin()) it--;
  87.  
  88.  
  89.                 int minpos = 0, mindiff = inf;
  90.                 for(int cnt = 0; cnt < 3 && it != ms.end(); cnt++, it++)
  91.                 {
  92.                     auto p = *it;
  93.                     int pos = p.second, val = p.first;
  94.                     if(pos == v) continue;
  95.                     if(abs(a[v] - val) < mindiff)
  96.                     {
  97.                         mindiff = abs(a[v] - val);
  98.                         minpos = pos;
  99.                     }
  100.                 }
  101.                 if(minpos != 0)
  102.                 {
  103.                     adj[v].insert(minpos);
  104.                     adj[minpos].insert(v);
  105.                     int a = minpos, b = v;
  106.                     if(a > b) swap(a, b);
  107.                     diff.insert({mindiff, {a, b}});
  108.                 }
  109.  
  110.             }
  111.         }
  112.     }
  113.     adj[x].clear();
  114. }
  115. int32_t main()
  116. {
  117. #define task "cpp"
  118.     if (fopen(task".inp", "r"))
  119.     {
  120.         freopen(task".inp", "r", stdin);
  121.         freopen(task".out", "w", stdout);
  122.     }
  123.     cin.tie(0)->sync_with_stdio(0);
  124.     cin >> n;
  125.     double s = sqrt((double)n);
  126.     double lg = log2((double)n);
  127.     lg = sqrt(lg);
  128.     s /= lg;
  129.     s += 50;
  130.     bsize = s;
  131.     FOR(i, 1, n)
  132.     {
  133.         cin >> a[i];
  134.         chia[i] = i / bsize;
  135.     }
  136.  
  137.     cin >> q;
  138.  
  139.     FOR(i, 1, q)
  140.     {
  141.         int l, r;
  142.         cin >> l >> r;
  143.         arr[i] = {i, l, r};
  144.     }
  145.  
  146.     sort(arr + 1, arr + q + 1, cmp);
  147.  
  148.  
  149.     FOR(i, 1, q)
  150.     {
  151.         int id = arr[i].id, l = arr[i].l, r = arr[i].r;
  152.         while(moleft < l) del(moleft++);
  153.         while(moleft > l) add(--moleft);
  154.         while(moright < r) add(++moright);
  155.         while(moright > r) del(moright--);
  156.         auto p = *diff.begin();
  157.         answer[id] = p.first;
  158.     }
  159.  
  160.     FOR(i, 1, q)
  161.     {
  162.         cout << answer[i] << '\n';
  163.     }
  164.  
  165.  
  166.     //printclock;
  167.     return 0;
  168. }
  169.  
Success #stdin #stdout 0.01s 15996KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ivF7Qa
language:
C++14 (clang 8.0)
created:
6 hours 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!