fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. using pii = pair<int, int>;
  7. const int N = 1e5 + 5;
  8. const int LG = 18;
  9. int n, q;
  10. int a[N], pos[N];
  11. bool ok[N];
  12. pii ans[N];
  13. struct query{
  14.     int l, r;
  15. } Q[N];
  16. void ckmin(pii &u, pii v) {
  17.     if (u.sc - u.ft > v.sc - v.ft) u = v;
  18. }
  19. void update(int &mmin, int &mmax, int i) {
  20.     mmin = min(mmin, a[i]);
  21.     mmax = max(mmax, a[i]);
  22.     ok[a[i]] = 1;
  23. }
  24. void reset(int l, int r) {
  25.     for (int i = l - 1; i <= r + 1; i++) ok[a[i]] = 0;
  26. }
  27. int mmin, mmax, posL, posR;
  28. void Calc_Via_Mid(int &idl, int &idr, int l, int r) {
  29.     while((posL > mmin || posR < mmax) && idl >= l && idr <= r) {
  30.         while(posL > mmin && idl >= l && idr <= r) {
  31.             if (!ok[posL]) {
  32.                 int tar = pos[posL];
  33.                 while(idl >= l && idl > tar) update(mmin, mmax, --idl);
  34.                 while(idr <= r && idr < tar) update(mmin, mmax, ++idr);
  35.             }
  36.             posL--;
  37.         }
  38.         while(posR < mmax && idl >= l && idr <= r) {
  39.             if (!ok[posR]) {
  40.                 int tar = pos[posR];
  41.                 while(idl >= l && idl > tar) update(mmin, mmax, --idl);
  42.                 while(idr <= r && idr < tar) update(mmin, mmax, ++idr);
  43.             }
  44.             posR++;
  45.         }
  46.     }
  47. }
  48. void ImproveViaMid(vector<int> &queries, int l, int r) {
  49.     if (queries.empty()) return;
  50.     int mid = l + r >> 1;
  51.     vector<pii> invals_left, invals_right;
  52.     mmin = a[mid + 1], mmax = a[mid + 1], posL = a[mid + 1], posR = a[mid + 1];
  53.     ok[a[mid + 1]] = 1;
  54.     for (int idl = mid, idr = mid + 1; idl >= l && idr <= r; idl--) {
  55.         update(mmin, mmax, idl);
  56.         Calc_Via_Mid(idl, idr, l, r);
  57.         if (idl >= l && idr <= r) invals_left.push_back({idl, idr});
  58.     }
  59.     reverse(invals_left.begin(), invals_left.end());
  60.     reset(l, r);
  61.  
  62.     mmin = a[mid], mmax = a[mid], posL = a[mid], posR = a[mid];
  63.     ok[a[mid]] = 1;
  64.     for (int idl = mid, idr = mid + 1; idl >= l && idr <= r; idr++) {
  65.         update(mmin, mmax, idr);
  66.         Calc_Via_Mid(idl, idr, l, r);
  67.         if (idl >= l && idr <= r) invals_right.push_back({idr, idl});
  68.     }
  69.  
  70.     for (int i: queries) {
  71.         int id_left = upper_bound(invals_left.begin(), invals_left.end(), (pii) {Q[i].l, N}) - invals_left.begin() - 1;
  72.         int id_right = lower_bound(invals_right.begin(), invals_right.end(), (pii) {Q[i].r, -1}) - invals_right.begin();
  73.         // if (id_left >= 0 && invals_left[id_left].ft <= Q[i].l && invals_left[id_left].sc >= Q[i].r) ckmin(ans[i], invals_left[id_left]);
  74.         // if (id_right < invals_right.size() && invals_right[id_right].ft <= Q[i].l && invals_right[id_right].sc >= Q[i].r) ckmin(ans[i], invals_right[id_right]);
  75.         // Không cần 2 if trên vẫn đúng
  76.         if (id_left >= 0 && id_right < invals_right.size()) {
  77.             int lim_l = min(invals_left[id_left].ft, invals_right[id_right].sc);
  78.             int lim_r = max(invals_left[id_left].sc, invals_right[id_right].ft);
  79.             if (lim_l <= Q[i].l && lim_r >= Q[i].r) ckmin(ans[i], {lim_l, lim_r});
  80.         }
  81.     }
  82.  
  83.     reset(l, r);
  84. }
  85.  
  86. void Improve(vector<int> queries, int l, int r) {
  87.     if (l >= r) {
  88.         for (int i: queries) ckmin(ans[i], {Q[i].l, Q[i].r});
  89.         return;
  90.     }
  91.     int mid = l + r >> 1;
  92.  
  93.     vector<int> queries_L, queries_R;
  94.     for (int i: queries) {
  95.         if (Q[i].r <= mid) queries_L.push_back(i);
  96.         if (Q[i].l > mid) queries_R.push_back(i);
  97.     }
  98.     Improve(queries_L, l, mid);
  99.     Improve(queries_R, mid + 1, r);
  100.     ImproveViaMid(queries, l, r);
  101. }
  102.  
  103. signed main() {
  104.     cin.tie(NULL)->sync_with_stdio(false);
  105.     if(ifstream("Input.inp")) {
  106.         freopen("Input.inp", "r", stdin);
  107.         freopen("Output.out", "w", stdout);
  108.     }
  109.     cin >> n;
  110.     for (int i = 1; i <= n; i++) {
  111.         cin >> a[i];
  112.         pos[a[i]] = i;
  113.     }
  114.     cin >> q;
  115.     for (int i = 1; i <= q; i++) {
  116.         cin >> Q[i].l >> Q[i].r;
  117.         ans[i] = {1, n};
  118.     }
  119.     vector<int> queries;
  120.     for (int i = 1; i <= q; i++) queries.push_back(i);
  121.     Improve(queries, 1, n);
  122.     for (int i = 1; i <= q; i++) cout << ans[i].ft << " " << ans[i].sc << "\n";
  123.     return 0;
  124. }
Success #stdin #stdout 0s 5328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/p65rDe
language:
C++ (gcc 8.3)
created:
9 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!