萌新刚学OI,全RE,球助

谢谢

#include<bits/stdc++.h>
using namespace std;
#define re register
#define ll long long
#define in inline
#define get getchar()
#define db double
in int read()
{
    int t=0,x=1; char ch=get;
    while ((ch<'0' || ch>'9') && ch!='-') ch=get;
    if (ch=='-') ch=get, x=-1;
    while (ch<='9' && ch>='0') t=t*10+ch-'0', ch=get;
    return t*x;
}
const int _=4e5+5;
struct region{
    int x,y;
}r[_];
ll n,m,k,add,a[_],sum[_];
in int cmp(region a,region b)
{
    return a.x<b.x;
}
in int lowbit(int x){
    return x&-x;
}
in void insert(int x,int y)
{
    for(re int i=x;i<=n;i+=lowbit(i)) sum[i]+=y;
}
in int query(int x)
{
    int ans=0;
    for(re int i=x;i>=1;i-=lowbit(i)) ans+=sum[i];
    return ans;
}
in int check(int x)
{
    priority_queue<int>q;
    int j=1,tot=0;
    memset(sum,0,sizeof(sum));
    for(re int i=1;i<=n;i++)
        insert(i,a[i]),insert(i+1,-a[i]);
    for (re int i=1;i<=n;i++)
    {
        int kkk=query(i);
        while(r[j].x<=i&&j<=m)
        {
            q.push(r[j].y);
            j++;
        }
        while(kkk<x&&q.top()>=i&&tot<=k&&!q.empty())
        {
            insert(i,add);
            insert(q.top()+1,-add);
            kkk=query(i);
            q.pop();
            tot++;
        }
        if(kkk<x||tot>k)return 0;
    }
    return 1;
}
int main()
{
    int t=read();
    while(t--)
    {
        ll maxx=0;
        n=read(),m=read(),k=read(),add=read();
        for (re int i=1;i<=n;i++) a[i]=read(),maxx=max(maxx,a[i]);
        for (re int i=1;i<=m;i++)
            r[i].x=read(),r[i].y=read();
        sort (r+1,r+1+m,cmp);
        int L=add,R=maxx+add,res,mid;
        while (L<=R)
        {
            mid=(L+R)>>1;
            if (check(mid)) res=mid,L=mid+1;
            else R=mid-1;
            //  cout<<mid<<endl;
        }
        cout<<res<<endl;
    }
}