AcWing 499. 聪明的质监员
原题链接
简单
作者:
我是java同学
,
2024-02-05 16:05:56
,
所有人可见
,
阅读 38
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010;
int n, m;
LL S;
int w[N], v[N];
LL s[N], cnt[N];
int L[N], R[N];
LL get(int W) {
for (int i = 1; i <= n; i ++ )
if (w[i] >= W) {
s[i] = s[i - 1] + v[i];
cnt[i] = cnt[i - 1] + 1;
} else {
s[i] = s[i - 1];
cnt[i] = cnt[i - 1];
}
LL res = 0;
for (int i = 0; i < m; i ++ )
res += (s[R[i]] - s[L[i] - 1]) *
(cnt[R[i]] - cnt[L[i] - 1]);
return res;
}
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 = 0; i < m; i ++ )
scanf("%d%d", &L[i], &R[i]);
int l = 0, r = 1e6 + 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (get(mid) >= S) l = mid;
else r = mid - 1;
}
printf("%lld", abs(min(get(r) - S, S - get(r + 1))));
return 0;
}