#13WA求助

_hud @ 2024-11-24 22:54:11

#include <bits/stdc++.h>
#define __init ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int long long

using namespace std;

const int N = 2e5+10;
int y, n, m, s, ans, mw, w[N], v[N], sw[N], sv[N], l[N], r[N];

void solve() {
    cin >> n >> m >> s;
    ans = s;
    for(int i = 1;i <= n;i++) {
        cin >> w[i] >> v[i];
        mw = max(mw, w[i]);
    }
    for(int i = 1;i <= m;i++) cin >> l[i] >> r[i];
    int pl = 0, pr = mw, mid, f;
    while(pl < pr) {
        mid = (pl+pr) >> 1;
        memset(sv, 0, sizeof(sv));
        memset(sw, 0, sizeof(sw));
        for(int i = 1;i <= n;i++) {
            f = (w[i] >= mid);
            sv[i] = sv[i-1] + f*v[i];
            sw[i] = sw[i-1] + f;
        }
        y = 0;
        for(int i = 1;i <= m;i++)
            y += (sw[r[i]] - sw[l[i]-1]) * (sv[r[i]]- sv[l[i]-1]);
        ans = min(ans, abs(s-y));
        if(y > s) pl = mid+1;
        else if(y < s) pr = mid;
        else break;
    }
    cout << min(ans, abs(s-y));
}

signed main() {
    __init;
    solve();
    return 0;
}

by luduoduo2023 @ 2024-11-30 20:11:23

#include<bits/stdc++.h>
using namespace std;
const int maxn=210000;
int n, m,w[maxn],v[maxn],ql[maxn],qr[maxn];
long long sumn[maxn],sumv[maxn],c1[maxn],c2[maxn],S;
long long check(int x) {
    long long all=0;
    memset(c1,0,sizeof(c1));
    for(int i=1; i<=n; i++) {
        c1[i]=c1[i-1];
        c2[i]=c2[i-1];
        if(x<=w[i]) {
            c1[i]++;
            c2[i]+=v[i];
        }
    }
    for(int i=1; i<=m; i++) {
        int ll=ql[i];
        int rr=qr[i];
        all+=(c1[rr]-c1[ll-1])*(c2[rr]-c2[ll-1]);
    }
    return all;
}
int main() {
    cin>>n>>m>>S;
    for(int i=1; i<=n; i++) cin>>w[i]>>v[i];
    for(int i=1; i<=m; i++) cin>>ql[i]>>qr[i];
    int l=0x3f3f3f3f,r=0,ans=0;
    for(int i=1; i<=n; i++) {
        l=min(w[i],l);
        r=max(w[i],r);
    }
    while(l<=r) {
        int m=(l+r)>>1;
        if(check(m)>=S) ans=m,l=m+1;
        else r=m-1;
    }
    cout<<min(abs(check(ans)-S),abs(check(ans+1)-S));
    return 0;
}

@_hud

by _hud @ 2024-12-01 14:34:57

@luduoduo2023 谢谢大佬!!!我知道哪里错了,右指针我忘记+1了,遗漏了全部不合格的情况.感谢帮助?