Page Contents

## C. Building a Fence SOLUTION CodeForces

### Educational Codeforces Round 101 (Rated for Div. 2)

- The first line contains a single integer t (1≤t≤104) — the number of test cases.
- The first line of each test case contains two integers n and k (2≤n≤2⋅105; 2≤k≤108) — the number of sections in the fence and the height of each section.
- The second line of each test case contains n integers h1,h2,…,hn (0≤hi≤108), where hi is the ground level beneath the i-th section.
- It’s guaranteed that the sum of n over test cases doesn’t exceed 2⋅105.

- For each test case print YES if it’s possible to build the fence that meets all rules. Otherwise, print NO.
- You may print each letter in any case (for example, YES, Yes, yes, yEs will all be recognized as positive answer).

- In the first test case, one of the possible fences is shown in the picture.
- In the second test case, according to the second rule, you should build both sections on the corresponding ground levels, and since k=3, h1=0, and h2=2 the first rule is also fulfilled.
- In the third test case, according to the second rule, you should build the first section on height 3 and the third section on height 2. According to the first rule, the second section should be on the height of at least 2 (to have a common side with the first section), but according to the third rule, the second section can be built on the height of at most h2+k−1=1.

**SOLUTION:**

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <utility>

#define INF 999999999

using namespace std;

typedef long long ll;

int t;

int n,k,h[200005];

int can[2][200005];

void init()

{

cin>>n>>k;

for(int i=1;i<=n;i++) cin>>h[i];

can[0][1]=h[1];

can[1][1]=h[1]+k;

}

void solve()

{

for(int i=2;i<n;i++)

{

int minh,maxh;

minh=h[i];

maxh=h[i]+k-1+k;

if(minh < can[1][i-1] && maxh > can[0][i-1])

{

can[0][i]=max(minh,can[0][i-1]-k+1);

can[1][i]=min(maxh,can[1][i-1]+k-1);

}

else

{

cout<<“NO”<<endl;

return;

}

}

if(h[n] < can[1][n-1] && h[n]+k > can[0][n-1] )

{

cout<<“YES”<<endl;

}

else

{

cout<<“NO”<<endl;

}

}

int main()

{

cin>>t;

while(t–)

{

init();

solve();

}

}

**RELATED :**

**A. Regular Bracket Sequence SOLUTION CodeForces**

**B. Red and Blue SOLUTION CodeForces**

**C. Building a Fence SOLUTION CodeForces**

**D. Ceil Divisions SOLUTION CodeForces**