fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int LOG = 20;            // 2^19 > 2e5 là đủ, dùng 20 cho an toàn
  5.  
  6. int main() {
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.  
  10.     int N, Q;
  11.     if (!(cin >> N >> Q)) return 0;
  12.     vector<int> H(N);
  13.     for (int i = 0; i < N; ++i) cin >> H[i];
  14.  
  15.     // 1) Nearest Greater to Left / Right
  16.     vector<int> L(N, -1), R(N, -1);
  17.     {
  18.         vector<int> st;
  19.         for (int i = 0; i < N; ++i) {
  20.             while (!st.empty() && H[st.back()] < H[i]) st.pop_back();
  21.             if (!st.empty()) L[i] = st.back();
  22.             st.push_back(i);
  23.         }
  24.     }
  25.     {
  26.         vector<int> st;
  27.         for (int i = N - 1; i >= 0; --i) {
  28.             while (!st.empty() && H[st.back()] < H[i]) st.pop_back();
  29.             if (!st.empty()) R[i] = st.back();
  30.             st.push_back(i);
  31.         }
  32.     }
  33.  
  34.     // 2) high / low neighbor
  35.     vector<int> hi(N, -1), lo(N, -1);
  36.     for (int i = 0; i < N; ++i) {
  37.         if (L[i] == -1 && R[i] == -1) {
  38.             hi[i] = lo[i] = -1;
  39.         } else if (L[i] == -1) {
  40.             hi[i] = R[i];
  41.             lo[i] = -1;
  42.         } else if (R[i] == -1) {
  43.             hi[i] = L[i];
  44.             lo[i] = -1;
  45.         } else {
  46.             if (H[L[i]] > H[R[i]]) {
  47.                 hi[i] = L[i];
  48.                 lo[i] = R[i];
  49.             } else {
  50.                 hi[i] = R[i];
  51.                 lo[i] = L[i];
  52.             }
  53.         }
  54.     }
  55.  
  56.     // 3) Doubling tables
  57.     // 3a) hi-jumps and max R along the path
  58.     vector<array<int, LOG>> up(N), rightJ(N), leftJ(N);
  59.     vector<array<int, LOG>> mxUp(N), mxLeft(N);
  60.  
  61.     for (int i = 0; i < N; ++i) {
  62.         up[i][0]    = hi[i];
  63.         mxUp[i][0]  = (R[i] == -1 ? -1 : R[i]);     // khi "đứng" ở i trước khi nhảy
  64.         rightJ[i][0]= R[i];
  65.         leftJ[i][0] = L[i];
  66.         mxLeft[i][0]= (R[i] == -1 ? -1 : R[i]);     // tương tự: đứng tại i
  67.     }
  68.     for (int k = 1; k < LOG; ++k) {
  69.         for (int i = 0; i < N; ++i) {
  70.             // hi
  71.             int mid = up[i][k-1];
  72.             if (mid == -1) { up[i][k] = -1; mxUp[i][k] = mxUp[i][k-1]; }
  73.             else {
  74.                 up[i][k]   = up[mid][k-1];
  75.                 mxUp[i][k] = max(mxUp[i][k-1], mxUp[mid][k-1]);
  76.             }
  77.             // right chain
  78.             int rmid = rightJ[i][k-1];
  79.             rightJ[i][k] = (rmid == -1 ? -1 : rightJ[rmid][k-1]);
  80.  
  81.             // left (L-chain) và max R trên các vị trí đã “đứng”
  82.             int lmid = leftJ[i][k-1];
  83.             if (lmid == -1) { leftJ[i][k] = -1; mxLeft[i][k] = mxLeft[i][k-1]; }
  84.             else {
  85.                 leftJ[i][k] = leftJ[lmid][k-1];
  86.                 mxLeft[i][k]= max(mxLeft[i][k-1], mxLeft[lmid][k-1]);
  87.             }
  88.         }
  89.     }
  90.  
  91.     auto farRightIndex = [&](int x, int D)->int {
  92.         if (x < 0) return -1;
  93.         int cur = x;
  94.         for (int k = LOG-1; k >= 0; --k) {
  95.             int y = rightJ[cur][k];
  96.             if (y != -1 && y <= D) cur = y;
  97.         }return cur; // last index ≤ D reachable by only R-jumps
  98.     };
  99.  
  100.     auto stepsToEnter = [&](int x, int C, int D)->pair<int,int> {
  101.         // trả về (index hạ cánh trong [C,D], số bước R) — nếu không thể, trả (-1,-1)
  102.         if (x == -1) return {-1,-1};
  103.         int cur = x, steps = 0;
  104.         // nhảy những khối vẫn còn < C
  105.         for (int k = LOG-1; k >= 0; --k) {
  106.             int y = rightJ[cur][k];
  107.             if (y != -1 && y < C && y <= D) {
  108.                 cur = y;
  109.                 steps += 1<<k;
  110.             }
  111.         }
  112.         int y = R[cur];
  113.         if (y == -1 || y > D) return make_pair(-1,-1);
  114.         ++steps; cur = y; // bước để vào [C,D]
  115.         if (cur < C || cur > D) return make_pair(-1,-1);
  116.         return {cur, steps};
  117.     };
  118.  
  119.     auto pickStart = [&](int A, int B, int D)->int {
  120.         // đi ngược theo L từ B, giữ max R trên các vị trí đã “đứng” ≤ D
  121.         int cur = B;
  122.         int mx = (R[cur] == -1 ? -1 : R[cur]);
  123.         if (mx > D) return -1;
  124.         for (int k = LOG-1; k >= 0; --k) {
  125.             int y = leftJ[cur][k];
  126.             if (y != -1 && y >= A) {
  127.                 int candMax = max(mx, mxLeft[cur][k]);
  128.                 if (candMax <= D) { // còn an toàn thì lùi tiếp
  129.                     mx  = candMax;
  130.                     cur = y;
  131.                 }
  132.             }
  133.         }
  134.         return cur;
  135.     };
  136.  
  137.     auto climbHiWhileSafe = [&](int cur, int C, int D, long long &used)->int {
  138.         // leo theo hi xa nhất sao cho:
  139.         // 1) mọi nút "đứng" có R ≤ D
  140.         // 2) từ điểm hạ cánh, đẩy phải tới cùng vẫn < C
  141.         for (int k = LOG-1; k >= 0; --k) {
  142.             int nxt = up[cur][k];
  143.             if (nxt == -1) continue;
  144.             if (mxUp[cur][k] > D) continue;                 // vi phạm (1)
  145.             int last = farRightIndex(nxt, D);
  146.             if (last >= C) continue;                        // vi phạm (2): đã có thể tới C
  147.             cur = nxt;
  148.             used += 1LL<<k;
  149.         }
  150.         return cur;
  151.     };
  152.  
  153.     while (Q--) {
  154.         int A,B,C,D; 
  155.         cin >> A >> B >> C >> D;
  156.  
  157.         int s = pickStart(A,B,D);
  158.         if (s == -1) { cout << -1 << '\n'; continue; }
  159.         if (s >= C && s <= D) { cout << 0 << '\n'; continue; }
  160.  
  161.         long long ans = 0;
  162.         int cur = s;
  163.         bool ok = true;
  164.  
  165.         while (true) {
  166.             // leo hi tối đa khi còn "an toàn" và vẫn chưa thể vào [C,D] chỉ bằng phải
  167.             long long used = 0;
  168.             cur = climbHiWhileSafe(cur, C, D, used);
  169.             ans += used;
  170.  
  171.             // nếu từ cur đẩy phải tới cùng vẫn chưa tới C -> thử 1 bước low
  172.             int last = farRightIndex(cur, D);
  173.             if (last < C) {
  174.                 if (lo[cur] == -1) { ok = false; break; }
  175.                 // bước lo phải hợp lệ vì hiện tại R[cur] ≤ D (được đảm bảo khi leo)
  176.                 cur = lo[cur];++ans;
  177.                 if (cur >= C && cur <= D) break;
  178.                 // lặp tiếp
  179.                 continue;
  180.             }
  181.  
  182.             // bây giờ chỉ cần nhảy phải tối thiểu để vào [C,D]
  183.             auto got = stepsToEnter(cur, C, D);
  184.             if (got.first == -1) { ok = false; break; }
  185.             ans += got.second;
  186.             cur  = got.first;
  187.             break;
  188.         }
  189.  
  190.         if (!ok) cout << -1 << '\n';
  191.         else     cout << ans << '\n';
  192.     }
  193.     return 0;
  194. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
7 2
3 2 1 6 4 5 7
4 4 6 6
1 3 5 6
stdout
copy 
2
1
https://ideone.com/c4vTV3
language:
C++14 (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!