Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <climits>
- constexpr int MAX = 1000010;
- int treeMin[4 * MAX], A[MAX];
- int treeMax[4 * MAX];
- void buildMin(int node, int ini, int fin) {
- if (ini == fin) {
- treeMin[node] = A[ini];
- } else {
- int mid = ini + (fin - ini) / 2;
- buildMin(2 * node, ini, mid);
- buildMin(2 * node + 1, mid + 1, fin);
- treeMin[node] = std::min(treeMin[2 * node], treeMin[2 * node + 1]);
- }
- }
- int queryMin(int node, int ini, int fin, int left, int right) {
- if (right < ini || fin < left) {
- return INT_MAX;
- }
- if (left <= ini && fin <= right) {
- return treeMin[node];
- }
- int mid = ini + (fin - ini) / 2;
- int p1 = queryMin(2 * node, ini, mid, left, right);
- int p2 = queryMin(2 * node + 1, mid + 1, fin, left, right);
- return std::min(p1, p2);
- }
- void buildMax(int node, int ini, int fin) {
- if (ini == fin) {
- treeMax[node] = A[ini];
- } else {
- int mid = ini + (fin - ini) / 2;
- buildMax(2 * node, ini, mid);
- buildMax(2 * node + 1, mid + 1, fin);
- treeMax[node] = std::max(treeMax[2 * node], treeMax[2 * node + 1]);
- }
- }
- int queryMax(int node, int ini, int fin, int left, int right) {
- if (right < ini || fin < left) {
- return INT_MIN;
- }
- if (left <= ini && fin <= right) {
- return treeMax[node];
- }
- int mid = ini + (fin - ini) / 2;
- int p1 = queryMax(2 * node, ini, mid, left, right);
- int p2 = queryMax(2 * node + 1, mid + 1, fin, left, right);
- return std::max(p1, p2);
- }
- int main( )
- {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(nullptr);
- int n, w, k;
- while (std::cin >> n >> w >> k) {
- if (n == 0 && w == 0 && k == 0) {
- break;
- }
- for (int i = 0; i < n; ++i) {
- std::cin >> A[i];
- }
- buildMin(1, 0, n - 1);
- buildMax(1, 0, n - 1);
- bool flag = true;
- for (int ti = w; ti < n; ++ti) {
- int low = abs(A[ti] - queryMin(1, 0, n - 1, ti - w, ti - 1));
- int hi = abs(A[ti] - queryMax(1, 0, n - 1, ti - w, ti - 1));
- if (low > k || hi > k) {
- flag = false;
- break;
- }
- }
- std::cout << (flag ? "Yes.\n" : "No.\n");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement