Untitled
raw download clone
CPP
views 14
,
size 2853 b
#include <bits/stdc++.h>
using namespace std;
#define pl(x) (x * 2 + 1)
#define pr(x) (x * 2 + 2)
int n, m;
vector<int> vec, arr, seg, ans;
void build(int index, int l, int r)
{
    if (l == r)
    {
        seg[index] = -(n - l);
        return;
    }
    int mid = (l + r) / 2;
    build(pl(index), l, mid);
    build(pr(index), mid + 1, r);
    seg[index] = min(seg[pl(index)], seg[pr(index)]);
}
void modify(int index, int ql, int qr, int l, int r, int value)
{
    if (ql >= l && qr <= r)
    {
        seg[index] += value;
        return;
    }
    int mid = (l + r) / 2;
    if (ql <= mid)
        modify(pl(index), ql, qr, l, mid, value);
    if (qr > mid)
        modify(pr(index), ql, qr, mid + 1, r, value);
    seg[index] = min(seg[pl(index)], seg[pr(index)]);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t, k,q,x,y;
    cin >> t;
    while (t--)
    {
        cin >> n >> m >> k;

        vec.clear();
        vec.resize(n);
        seg.clear();
        seg.resize(n << 2);
        arr.clear();
        arr.resize(m);
        ans.clear();
        ans.resize(m);

        for (int i = 0; i < n; i++){
            cin >> vec[i];
            vec[i]=k-vec[i];
        }
        sort(vec.begin(), vec.end());
        for (int i = 0; i < m; i++)
            cin >> arr[i];
        build(0, 0, n - 1);
        for (int i = 0; i < m; i++)
        {
            if (i < n)
            {
                auto u = upper_bound(vec.begin(), vec.end(), arr[i]);
                if (u != vec.begin())
                    modify(0, 0, upper_bound(vec.begin(), vec.end(), arr[i]) - 1 - vec.begin(), 0, n - 1, 1);
                //cerr<<"i= "<<i<<" change +1 to "<<upper_bound(vec.begin(), vec.end(), arr[i]) - 1 - vec.begin()<<'\n';
            }
            else
            {
                auto u = upper_bound(vec.begin(), vec.end(), arr[i]);
                if (u != vec.begin())
                    modify(0, 0, upper_bound(vec.begin(), vec.end(), arr[i]) - 1 - vec.begin(), 0, n - 1, 1);
                 //cerr<<"i= "<<i<<" change +1 to "<<upper_bound(vec.begin(), vec.end(), arr[i]) - 1 - vec.begin()<<'\n';
                auto u2 = upper_bound(vec.begin(), vec.end(), arr[i - n]);
                if (u2 != vec.begin())
                    modify(0, 0, upper_bound(vec.begin(), vec.end(), arr[i - n]) - 1 - vec.begin(), 0, n - 1, -1);
                 //cerr<<"i= "<<i<<" change -1 to "<<upper_bound(vec.begin(), vec.end(), arr[i-m]) - 1 - vec.begin()<<'\n';
            }
            if (i >= n-1)
                ans[i - n+1] = seg[0];
        }
        cin>>q;
        for(int i=0;i<q;i++)
        {
            cin>>x>>y;
            if(ans[x-1]>=0)cout<<"1\n";
            else cout<<"0\n";
        }
    }

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