Cake Assembly Line

标签：cakes Assembly conveyor chocolate test example Cake Line line

Cake Assembly Line time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

A cake assembly line in a bakery was once again optimized, and now n cakes are made at a time! In the last step, each of the n cakes should be covered with chocolate.

Consider a side view on the conveyor belt, let it be a number line. The i-th cake occupies the segment [ai−w,ai+w][−,+] on this line, each pair of these segments does not have common points. Above the conveyor, there are n dispensers, and when a common button is pressed, chocolate from the i-th dispenser will cover the conveyor segment [bi−h,bi+h][−ℎ,+ℎ]. Each pair of these segments also does not have common points.

Cakes and dispensers corresponding to the first example.

The calibration of this conveyor belt part has not yet been performed, so you are to make it. Determine if it's possible to shift the conveyor so that each cake has some chocolate on it, and there is no chocolate outside the cakes. You can assume that the conveyour is long enough, so the cakes never fall. Also note that the button can only be pressed once.

In the first example we can shift the cakes as shown in the picture. Input

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤1051≤≤105). The description of the test cases follows.

The first line of each test case contains three integers n, w, and hℎ (1≤n≤1051≤≤105; 1≤w,h≤1051≤,ℎ≤105; h≤wℎ≤) — the number of cakes and dispensers, as well as the halfwidths of cakes and segments on which the chocolate is dispensed.

The second line contains n integers a11, a22, ..., an (1≤ai≤1091≤≤109) — the positions of the cakes centers. It is guaranteed that ai+w<ai+1−w+<+1− for all i.

The third line contains n integers b11, b22, ..., bn (1≤bi≤1091≤≤109) — the positions of the dispensers. It is guaranteed that bi+h<bi+1−h+ℎ<+1−ℎ for all i.

It is guaranteed that the sum of n over all test cases does not exceed 105105.

Output

For each test case output "YES", if it's possible to shift the conveyor in such a way that each cake ends up with some chocolate, and no chocolate is outside the cakes, and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Example input Copy 4 3 10 5 65 95 165 40 65 145 5 2 1 1 6 11 16 21 4 9 14 19 24 3 3 2 13 22 29 5 16 25 4 4 1 27 36 127 136 35 50 141 144 output Copy

YES
YES
NO
YES

Note

The first example is shown in the figures in the statement.

In the second example, we can move the conveyor, for example, so that the centers of the cakes are at 4,9,14,19,244,9,14,19,24.

In the third example, we can't move the conveyor accordingly.

//设向右为正方向
//蛋糕如果需要移动到最右端点,那就是rb-ra
//最左端点的话就是lb-la
//蛋糕只需要向右移动{l,r}这个区间就是合法的
//对于每个蛋糕都有一个这样的区间,只需要判断每个区间是否都有交集就可以了
#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10,mod=1e9+7;
string s;
long long n,t,a[N],b[N],res,num,ans,w,h,l=-1e9,r=1e9;
bool vis[N];
int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>w>>h;
        l=-1e9,r=1e9;
        for(int i=0;i<n;i++) cin>>a[i];
        for(int i=0;i<n;i++) cin>>b[i];
        for(int i=0;i<n;i++){
            l=max(l,b[i]+h-a[i]-w),r=min(r,b[i]-h-a[i]+w);//判断是否有交集
            if(l>r){
                cout<<"NO"<<endl;
                goto nexts;
            }
        }
        cout<<"YES"<<endl;
        nexts:;
    }
    return 0;
}

 

标签：cakes,Assembly,conveyor,chocolate,test,example,Cake,Line,line
From： https://www.cnblogs.com/o-Sakurajimamai-o/p/17513875.html