申请添加 hack（含数据生成器），34 题解代码遭殃！

根据题目给出的数据范围，y 可能超过 64 位有符号整数的表示范围，当然也超过了 64 位无符号整数的表示范围。

考虑每个 y_i，乘号左边的最大值可达 n=2\times10^5（w_j\ge W 全部成立），右边可达 n*v_{max}=2\times10^{11}，也就是说每个 y_i 的最大值可达 4\times10^{16}。
同时 m 最大可取 2\times10^5，这就意味着真实的 y 值可达到 8\times10^{21}，远超 64 位无符号整数的表示范围。

一种解决方法是在加 y_i 的过程中剪枝，如果当前累计的 y 达到某一阈值，则直接退出，这个阈值的最小值应为 2s+1，如果二分法比较巧妙可以是 2s。

hack 数据生成器

输入

#include <bits/stdc++.h>
using namespace std;

const int n = 200000;
const int m = 200000;
const long long s = 1000000000000ll;

int main(){
    freopen("P1314.in", "w", stdout);
    cout << n << ' ' << m << ' ' << s << endl;
    for(int i=1; i<=n; ++i){
        cout << 1 << ' ' << 200000 << endl;
    }
    for(int i=1; i<=m; ++i){
        cout << 1 << ' ' << n << endl;
    }
    return 0;
}

输出

1000000000000

hack 成果

正解对比实例

应用剪枝可以过上述 hack 的代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long int64;

int n, m;
int64 s;
int w[200001], v[200001];
int l[200000], r[200000];

int sum1[200001]; int64 sum2[200001];

int64 check(int W){
    for(int i=1; i<=n; ++i){
        sum1[i] = sum1[i-1]+(w[i]>=W);
        sum2[i] = sum2[i-1]+(w[i]>=W?v[i]:0);
    }
    int64 res = 0;
    for(int i=0; i<m; ++i){
        res += (sum1[r[i]]-sum1[l[i]-1])*(sum2[r[i]]-sum2[l[i]-1]);
        if(res > (s<<1)) break;
    }
    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 res = lower_bound((char*)1, (char*)1000000, 0, [](char& W, int _){
        return check(&W-(char*)0)>s;
    })-(char*)0;
    int64 error = min(s-check(res), check(res-1)-s);
    printf("%lld", error);
    return 0;
}

其中的剪枝语句为 if(res > (s<<1)) break;

去掉上面的剪枝语句不可以过上述 hack 的代码，但是当前数据 AC，其输出结果：

-4866735412730990592

hack 题解

发这篇帖子时，没有看到一篇题解明确指出 y 值可能超出 int64。

以下仅包括给出 C++ 代码的题解，没有测试代码是否能在当前测试数据下 AC。

遭殃题解 #1 输出：

4557430888798830399

遭殃题解 #2 输出：

40000000000000

遭殃题解 #3 输出：

999999999999999

遭殃题解 #4 输出：

4866735412730990592

遭殃题解 #5 输出：

4866735412730990592

遭殃题解 #6 输出：

4866735412730990592

遭殃题解 #7 输出：

4866735412730990592

补充：本地编译报错重复定义 abs 函数，以上是去掉这个定义的结果。

遭殃题解 #8 RE。
补充：将 §替换为 sect 的结果。

遭殃题解 #9 输出：

4866735412730990592

遭殃题解 #10 输出：

99999999999

遭殃题解 #11 输出：

4866735412730990592

遭殃题解 #12 输出：

-4866735412730990592

遭殃题解 #13 输出：

4866735412730990592

遭殃题解 #14 输出：

140737488355327

遭殃题解 #15 输出：

999999999999

遭殃题解 #16 输出：

4557430888798830399

遭殃题解 #17 输出：

40000000000000

遭殃题解 #18 输出：

12425374554373

遭殃题解 #19 输出：

12425374554373

遭殃题解 #20 输出：

1073741824000

遭殃题解 #21 输出：

17802464409370431

遭殃题解 #22 输出：

-4866735412730990592

遭殃题解 #23 输出：

547599908735

遭殃题解 #24 输出：

69540876599103

遭殃题解 #25 输出：

999999999999999

遭殃题解 #26 输出：

9999999999999999

遭殃题解 #27 输出：

-4866735412730990592

遭殃题解 #28 输出：

1000000000000000000

遭殃题解 #29 输出：

1528459781128654848

遭殃题解 #30 输出：

-4866735412730990592

遭殃题解 #31 输出：

4866735412730990592

遭殃题解 #32 输出：

100000000000000

遭殃题解 #33 输出：

12425374554373

遭殃题解 #34 输出：

12425374554373