Advertisement
AlejandroGY

Untitled

Mar 8th, 2018
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.05 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <climits>
  4.  
  5. constexpr int MAX = 1000010;
  6. int treeMin[4 * MAX], A[MAX];
  7. int treeMax[4 * MAX];
  8.  
  9. void buildMin(int node, int ini, int fin) {
  10.     if (ini == fin) {
  11.         treeMin[node] = A[ini];
  12.     } else {
  13.         int mid = ini + (fin - ini) / 2;
  14.         buildMin(2 * node, ini, mid);
  15.         buildMin(2 * node + 1, mid + 1, fin);
  16.         treeMin[node] = std::min(treeMin[2 * node], treeMin[2 * node + 1]);
  17.     }
  18. }
  19.  
  20. int queryMin(int node, int ini, int fin, int left, int right) {
  21.     if (right < ini || fin < left) {
  22.         return INT_MAX;
  23.     }
  24.     if (left <= ini && fin <= right) {
  25.         return treeMin[node];
  26.     }
  27.     int mid = ini + (fin - ini) / 2;
  28.     int p1 = queryMin(2 * node, ini, mid, left, right);
  29.     int p2 = queryMin(2 * node + 1, mid + 1, fin, left, right);
  30.     return std::min(p1, p2);
  31. }
  32.  
  33. void buildMax(int node, int ini, int fin) {
  34.     if (ini == fin) {
  35.         treeMax[node] = A[ini];
  36.     } else {
  37.         int mid = ini + (fin - ini) / 2;
  38.         buildMax(2 * node, ini, mid);
  39.         buildMax(2 * node + 1, mid + 1, fin);
  40.         treeMax[node] = std::max(treeMax[2 * node], treeMax[2 * node + 1]);
  41.     }
  42. }
  43.  
  44. int queryMax(int node, int ini, int fin, int left, int right) {
  45.     if (right < ini || fin < left) {
  46.         return INT_MIN;
  47.     }
  48.     if (left <= ini && fin <= right) {
  49.         return treeMax[node];
  50.     }
  51.     int mid = ini + (fin - ini) / 2;
  52.     int p1 = queryMax(2 * node, ini, mid, left, right);
  53.     int p2 = queryMax(2 * node + 1, mid + 1, fin, left, right);
  54.     return std::max(p1, p2);
  55. }
  56.  
  57. int main( )
  58. {
  59.     std::ios_base::sync_with_stdio(false);
  60.     std::cin.tie(nullptr);
  61.  
  62.     int n, w, k;
  63.     while (std::cin >> n >> w >> k) {
  64.         if (n == 0 && w == 0 && k == 0) {
  65.             break;
  66.         }
  67.  
  68.         for (int i = 0; i < n; ++i) {
  69.             std::cin >> A[i];
  70.         }
  71.        
  72.         buildMin(1, 0, n - 1);
  73.         buildMax(1, 0, n - 1);
  74.  
  75.         bool flag = true;
  76.         for (int ti = w; ti < n; ++ti) {
  77.             int low = abs(A[ti] - queryMin(1, 0, n - 1, ti - w, ti - 1));
  78.             int hi = abs(A[ti] - queryMax(1, 0, n - 1, ti - w, ti - 1));
  79.             if (low > k || hi > k) {
  80.                 flag = false;
  81.                 break;
  82.             }
  83.         }
  84.         std::cout << (flag ? "Yes.\n" : "No.\n");
  85.     }
  86. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement