20分求调！

smallpeople @ 2024-05-15 17:28:28

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200005;

ll n,m,s,ans = 0x3f3f3f3f3f3f3f3f;
int w[N],v[N],a[N],b[N],l[N],r[N],lt,rt = -1;

int check(int ww)
{
    int sum = 0;
    for(int i = 1;i <= n;i ++)
    {
        a[i] = a[i - 1];
        b[i] = b[i - 1];
        if(w[i] >= ww)a[i] ++,b[i] += v[i];
    }
    for(int i = 1;i <= m;i ++)
        sum += (a[r[i]] - a[l[i] - 1]) * (b[r[i]] - b[l[i] - 1]);
    ans = min(ans,abs(s - sum));
    if(s - sum < 0)return 1;
    else return 0;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m>>s;
    for(int i = 1;i <= n;i ++)
    {
        cin>>w[i]>>v[i];
        rt = max(rt,w[i]);
    }
    for(int i = 1;i <= m;i ++)
        cin>>l[i]>>r[i];

    while(lt <= rt)
    {
        int mid = (lt + rt) / 2;
        if(check(mid))lt = mid + 1;
        else rt = mid - 1;
    }
    cout<<ans<<'\n';

    return 0;
}

by 123huchenghao @ 2024-06-30 16:34:50

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;

int n, m, w[200010], v[200010], l[200010], r[200010];
long long cts[200010], vs[200010];
long long s, ans = 1e13;

long long check(long long x) {  // return y
    for (int i = 1; i <= n; i++) {
        cts[i] = cts[i - 1] + (w[i] >= x);
        vs[i] = vs[i - 1] + (w[i] >= x) * v[i];
    }
    long long sum = 0;
    for (int i = 1; i <= m; i++)
        sum += (cts[r[i]] - cts[l[i] - 1]) * (vs[r[i]] - vs[l[i] - 1]);
    return sum;
}

int main() {
    scanf("%d%d%lld", &n, &m, &s);
    for (int i = 1; i <= n; i++) scanf("%d%d", w + i, v + i);
    for (int i = 1; i <= m; i++) scanf("%d%d", l + i, r + i);

    long long L = 0, R = 1e13;
    while (L < R - 1) {
        long long mid = L + R >> 1;
        long long y = check(mid);
        if (s - y > 0)
            R = mid;
        else
            L = mid;
    }

    printf("%lld\n", min(abs(check(L) - s), abs(check(R) - s)));

    return 0;
}