fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Solve offline queries to find the minimum absolute difference between any two numbers in a subarray
  5.  
  6. struct Query {
  7.     int left;
  8.     int right;
  9.     int index;
  10. };
  11.  
  12. constexpr int MAXN = 300000 + 5;
  13. constexpr int BLOCK_SIZE = 400;
  14. constexpr int INF = 1e9;
  15.  
  16. int nextPos[MAXN];       // Next element in the linked list
  17. int prevPos[MAXN];       // Previous element in the linked list
  18. int compressed[MAXN];    // Compressed original array values
  19. int original[MAXN];      // Original array values
  20. int answer[MAXN];        // Answer for each query
  21. int dp[BLOCK_SIZE + 5][MAXN];  // Precomputed results for short intervals
  22. int blockMin[MAXN];      // Minimum difference for intervals spanning a block
  23. map<int,int> frequencyMap;
  24. vector<Query> queriesByBlock[MAXN / BLOCK_SIZE + 5];
  25.  
  26. // Comparator: sort queries in descending order of right endpoint
  27. bool compareByRightDesc(const Query &a, const Query &b) {
  28.     return a.right > b.right;
  29. }
  30.  
  31. // Insert position x into the active set and return the minimum neighbor difference
  32. int insertPosition(int x) {
  33.     int best = INF;
  34.     if (prevPos[x] >= 1) {
  35.         best = min(best, original[x] - original[prevPos[x]]);
  36.     }
  37.     if (nextPos[x] <= MAXN - 1) {
  38.         best = min(best, original[nextPos[x]] - original[x]);
  39.     }
  40.     nextPos[prevPos[x]] = x;
  41.     prevPos[nextPos[x]] = x;
  42.     return best;
  43. }
  44.  
  45. // Remove position x from the active set
  46. void removePosition(int x) {
  47.     nextPos[prevPos[x]] = nextPos[x];
  48.     prevPos[nextPos[x]] = prevPos[x];
  49. }
  50.  
  51. int main() {
  52.     ios::sync_with_stdio(false);
  53.     cin.tie(nullptr);
  54.  
  55.     int n;
  56.     cin >> n;
  57.  
  58.     // Read and store original values
  59.     for (int i = 1; i <= n; ++i) {
  60.         cin >> compressed[i];
  61.         original[i] = compressed[i];
  62.     }
  63.  
  64.     // Coordinate compression
  65.     sort(original + 1, original + n + 1);
  66.     original[0] = -INF;
  67.     original[n + 1] = INF;
  68.  
  69.     // Assign unique ranks to duplicates
  70.     for (int i = 1; i <= n; ++i) {
  71.         int rank = lower_bound(original + 1, original + n + 1, compressed[i]) - original;
  72.         compressed[i] = rank + (frequencyMap[rank]++);
  73.     }
  74.  
  75.     int q;
  76.     cin >> q;
  77.  
  78.     // Group queries by block of left endpoint
  79.     for (int i = 1; i <= q; ++i) {
  80.         int l, r;
  81.         cin >> l >> r;
  82.         int blockId = (l - 1) / BLOCK_SIZE;
  83.         queriesByBlock[blockId].push_back({l, r, i});
  84.     }
  85.  
  86.     // Sort queries in each block by decreasing right endpoint
  87.     int numBlocks = (n + BLOCK_SIZE - 1) / BLOCK_SIZE;
  88.     for (int b = 0; b < numBlocks; ++b) {
  89.         sort(queriesByBlock[b].begin(), queriesByBlock[b].end(), compareByRightDesc);
  90.     }
  91.  
  92.     // Precompute dp for small intervals (length <= BLOCK_SIZE)
  93.     for (int len = 1; len <= min(BLOCK_SIZE, n); ++len) {
  94.         for (int start = 1; start + len - 1 <= n; ++start) {
  95.             if (len == 1) {
  96.                 dp[len][start] = INF;
  97.             } else {
  98.                 dp[len][start] = min({
  99.                     dp[len - 1][start],
  100.                     dp[len - 1][start + 1],
  101.                     abs(compressed[start] - compressed[start + len - 1])
  102.                 });
  103.             }
  104.         }
  105.     }
  106.  
  107.     // Process each block
  108.     for (int b = 0; b < numBlocks; ++b) {
  109.         int leftBound = b * BLOCK_SIZE + 1;
  110.         int rightBound = min(n, (b + 1) * BLOCK_SIZE);
  111.  
  112.         // Initialize linked lists
  113.         for (int i = 0; i <= n + 1; ++i) {
  114.             prevPos[i] = i - 1;
  115.             nextPos[i] = i + 1;
  116.         }
  117.  
  118.         // Remove all positions outside [1..rightBound]
  119.         for (int i = 1; i < leftBound; ++i) removePosition(compressed[i]);
  120.         for (int i = rightBound + 1; i <= n; ++i) removePosition(compressed[i]);
  121.  
  122.         // Build blockMin from rightBound to n
  123.         int currentMin = INF;
  124.         for (int i = rightBound + 1; i <= n; ++i) {
  125.             currentMin = min(currentMin, insertPosition(compressed[i]));
  126.             blockMin[i] = currentMin;
  127.         }
  128.  
  129.         // Process queries in block b
  130.         int ptr = n;
  131.         for (auto &query : queriesByBlock[b]) {
  132.             int l = query.left;
  133.             int r = query.right;
  134.  
  135.             // If interval length is small, use dp table
  136.             if (r - l + 1 <= BLOCK_SIZE) {
  137.                 answer[query.index] = dp[r - l + 1][l];
  138.                 continue;
  139.             }
  140.  
  141.             // Use precomputed blockMin and dynamic insertion
  142.             int res = blockMin[r];
  143.  
  144.             // Shrink ptr to r
  145.             while (ptr > r) {
  146.                 removePosition(compressed[ptr--]);
  147.             }
  148.  
  149.             // Temporarily remove positions left of leftBound
  150.             for (int i = leftBound; i < rightBound; ++i) removePosition(compressed[i]);
  151.  
  152.             // Insert positions from r-1 down to l
  153.             int tmpMin = res;
  154.             for (int i = rightBound - 1; i >= l; --i) {
  155.                 tmpMin = min(tmpMin, insertPosition(compressed[i]));
  156.             }
  157.             res = tmpMin;
  158.  
  159.             // Restore removed positions
  160.             for (int i = l - 1; i >= leftBound; --i) insertPosition(compressed[i]);
  161.  
  162.             answer[query.index] = res;
  163.         }
  164.     }
  165.  
  166.     // Output answers
  167.     for (int i = 1; i <= q; ++i) {
  168.         cout << answer[i] << "\n";
  169.     }
  170.  
  171.     return 0;
  172. }
  173.  
Success #stdin #stdout 0.01s 5500KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/Hn9ZfB
language:
C++14 (gcc 8.3)
created:
6 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!