求调20pts AC#1 #2

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0 ,f = 1;
    char ch = getchar();
    while('0' > ch || ch > '9'){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while('0' <= ch && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
const int N = 2e5 + 5;
int T ,n ,m ,k ,a ,A[N] ,c[N];
struct stu {
    int Left ,Right;
    bool operator <(const stu &a)const {
        if(Left != a.Left) return Left < a.Left;
        else return Right < a.Right;
    }
}t[N];
int lowbit(int x) {
    return x & (-x);
}
void updata(int x,int a) {
    for(int i = x;i <= n;i += lowbit(i)) {
        c[i] += a;
    }
    return ;
}
int query(int x) {
    int sum = 0;
    for(int i = x;i > 0;i -= lowbit(i)) {
        sum += c[i];
    }
    return sum;
}
priority_queue<int>que;
bool check(int x) {
    while(!que.empty())que.pop();
    memset(c ,0 ,sizeof(c));
    int tmpt = 0;
    for(int i = 1 ,l = 1;i <= n;++ i) {
        int tmp = A[i] + query(i);
        if(tmp < x) {
            while(t[l].Left <= i && l <= m) {
                que.push(t[l].Right);
                ++ l;
            }
            int tx = (x - tmp + a - 1) / a;
            tmpt += tx;
            if(tmp > k)return false;
            for(int j = 1;j <= tx;++ j) {
                if(que.empty() || que.top() < i)return false;
                updata(i ,a);
                updata(que.top() + 1 ,-a);
                que.pop();
            }
        }
    }
    return (tmpt <= k);
}
signed main() {
    T = read();
    while(T --) {
        memset(A ,0 ,sizeof(A));
        n = read(); m = read(); k = read(); a = read();
        for(int i = 1;i <= n;++ i) A[i] = read();
        for(int j = 1;j <= m;++ j) {
            t[j].Left = read(); t[j].Right = read();
        }
        sort(t + 1 ,t + m + 1);
        int l = 1 ,r = 2e8 + 5;
        while(l < r) {
            int mid = l + r + 1 >> 1;
            if(check(mid)) {
                l = mid;
            }
            else r = mid - 1;
        }
        cout << l << '\n';
    }
    return 0;
}