Untitled
raw download clone
CPP
views 14
,
size 3873 b
#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) (x&-x)
#define mod 1000000007LL
#define endl '\n'
#define SZ(x) (int)x.size()
#define PB push_back
#define eps 1e-6
#define FZ(x) memset(x,0,sizeof(x))
#define cl(x) (x<<1)
#define cr(x) (x<<1|1)

using namespace std;

mt19937 gen(880907);

struct seg_tree{
	static const int MXN=2e5+5,NO_TAG=0; // to be set
	ll a[MXN],val[MXN*4],tag[MXN*4],v;
	int n,ql,qr;
    void init(){
        memset(val,0,sizeof(val));
        memset(tag,0,sizeof(tag));
    }
	void push(int i,int l,int r){
		if(tag[i]!=NO_TAG){
			val[i]+=tag[i]; // update by tag
			if(l!=r){
				tag[cl(i)]+=tag[i]; // push
				tag[cr(i)]+=tag[i]; // push
			}
			tag[i]=NO_TAG;
		}
	}
	void pull(int i,int l,int r){
		int mid=(l+r)>>1;
		push(cl(i),l,mid);push(cr(i),mid+1,r);
		val[i]=min(val[cl(i)],val[cr(i)]); // pull
	}
	void build(int i,int l,int r){
		if(l==r){
			val[i]=a[l]; // set value
			return;
		}
		int mid=(l+r)>>1;
		build(cl(i),l,mid);build(cr(i),mid+1,r);
		pull(i,l,r);
	}
	void update(int i,int l,int r){
		push(i,l,r);
		if(ql<=l&&r<=qr){
			tag[i]+=v; // update tag
			return;
		}
		int mid=(l+r)>>1;
		if(ql<=mid) update(cl(i),l,mid);
		if(qr>mid) update(cr(i),mid+1,r);
		pull(i,l,r);
	}
	void query(int i,int l,int r){
		push(i,l,r);
		if(ql<=l&&r<=qr){
			v=min(v,val[i]); // update answer
			return;
		}
		int mid=(l+r)>>1;
		if(ql<=mid) query(cl(i),l,mid);
		if(qr>mid) query(cr(i),mid+1,r);
	}
}tree;


ll n,m,k;
vector<bool> v;
vector<ll> idx;
vector<ll> arr,brr;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m>>k;
        int cnt=0;
        if(n>m) goto query;
        tree.init();
        v.clear();v.resize(m,0);
        arr.clear();arr.resize(n);
        brr.clear();brr.resize(m);
        idx.clear();
        for(int i=0;i<n;i++)    cin>>arr[i];
        for(int i=0;i<m;i++)    cin>>brr[i];
        for(int i=0;i<n;i++){
            arr[i]=k-arr[i];
        }
        sort(arr.begin(),arr.end());
        idx=arr;
        idx.resize(unique(idx.begin(),idx.end())-idx.begin());
        for(int i=idx.size()-1;i>=0;i--){
            cnt-=upper_bound(arr.begin(),arr.end(),idx[i])-lower_bound(arr.begin(),arr.end(),idx[i]);
            tree.ql=tree.qr=i;
            tree.v=cnt;
            tree.update(0,0,idx.size()-1);
        }
        for(int i=0;i<n;i++){
            int pos=upper_bound(idx.begin(),idx.end(),brr[i])-idx.begin()-1;
            if(pos>=0){
                tree.ql=0;
                tree.qr=pos;
                tree.v=1;
                tree.update(0,0,idx.size()-1);
            }
        }
        for(int i=n;i<m;i++){
            tree.ql=0;
            tree.qr=idx.size()-1;
            tree.v=1e9;
            tree.query(0,0,idx.size()-1);
            v[i-n]=tree.v>=0;
            int pos=upper_bound(idx.begin(),idx.end(),brr[i])-idx.begin()-1;
            if(pos>=0){
                tree.ql=0;
                tree.qr=pos;
                tree.v=1;
                tree.update(0,0,idx.size()-1);
            }
            pos=upper_bound(idx.begin(),idx.end(),brr[i-n])-idx.begin()-1;
            if(pos>=0){
                tree.ql=0;
                tree.qr=pos;
                tree.v=-1;
                tree.update(0,0,idx.size()-1);
            }
        }
        tree.ql=0;
        tree.qr=idx.size()-1;
        tree.v=1e9;
        tree.query(0,0,idx.size()-1);
        v[m-n]=tree.v>=0;
        query:;
        int q;
        cin>>q;
        while(q--){
            int l,r;
            cin>>l>>r;
            if(r-l+1<n){
                cout<<0<<endl;
            }
            else
                cout<<v[l-1]<<endl;
        }
    }

    return 0;
}
close fullscreen
Login or Register to edit or fork this paste. It's free.