【二分+前缀和】P1314 聪明的质监员

 1 #include<iostream>
 2 #include<string>
 3 #include<queue>
 4 #include<stack>
 5 #include<vector>
 6 #include<map>
 7 #include<cstdio>
 8 #include<cstdlib>
 9 #include<algorithm>
10 #include<set>
11 #include<list>
12 #include<iomanip>
13 #include<cstring>
14 #include<cmath>
15 #include<limits>
16 using namespace std;
17 
18 #define au auto
19 #define debug(i) cout<<"<debug> "<<i<<" <\debug>"<<endl
20 #define mfor(i,a,b) for(register int i=(a);i<=(b);i++)
21 #define mrep(i,a,b) for(register int i=(a);i>=(b);i--)
22 #define LLL __int128
23 #define Re register
24 #define il inline
25 #define mem(a,b) memset(a,(b),sizeof(a))
26 typedef pair<int, int> intpair;
27 typedef pair<long long int, long long int> llpair;
28 typedef long long int LL;
29 const int INF = 0x3f3f3f3f;
30 const long long int INFLL = 0x3f3f3f3f3f3f3f3f;
31 
32 const int maxn = 200010;
33 int w[maxn], v[maxn], l[maxn], r[maxn];
34 LL tot[maxn], num[maxn];
35 LL s, sum;
36 LL ans;
37 int n, m;
38 int maxw = -INF;
39 int minw = INF;
40 
41 bool check(int x)
42 {
43     LL y = 0;
44     sum = 0;
45     mem(num, 0);
46     mem(tot, 0);
47     mfor(i, 1, n)
48     {
49         if (w[i] >= x)
50         {
51             num[i] = num[i - 1] + 1;
52             tot[i] = tot[i - 1] + v[i];
53         }
54         else 
55         {
56             num[i] = num[i - 1];
57             tot[i] = tot[i - 1];
58         }
59     }
60     mfor(i, 1, m)
61     {
62         y += (num[r[i]] - num[l[i] - 1]) * (tot[r[i]] - tot[l[i] - 1]);
63     }
64     sum = y - s;
65     if (sum < 0) sum = -sum;
66     return y > s;
67 }
68 int main() 
69 {
70     cin >> n >> m >> s;
71     mfor(i, 1, n)
72     {
73         cin >> w[i] >> v[i];
74         maxw = max(maxw, w[i]);
75         minw = min(minw, w[i]);
76     }
77     mfor(i, 1, m)
78     {
79         cin >> l[i] >> r[i];
80     }
81     int left = minw - 1, right = maxw + 1;
82     ans = INFLL;
83     while (left < right)
84     {
85         int mid = (left + right) >> 1;
86         if (check(mid))  left = mid + 1;
87         else right = mid;
88         ans = min(ans, sum);
89     }
90     cout << ans;
91     return 0;
92 }