ABC298F离散化STL坐标行列之和最大值统计

#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k;
map <long long, long long> x, y, f;
multimap <long long, long long> v;
long long ans, M=1e9+7;
int main(){
    scanf("%d", &n);
    while(n--){
        scanf("%d%d%d", &i, &j, &k);
        x[i] += k, y[j] += k, f[i*M+j] = k;
    }//x记录行之和，y记录列之和，f记录该位置的数字
    for(auto p=y.begin(); p!=y.end(); p++){
        v.insert(make_pair(p->second, p->first));
    }//列之和排序，确定行后，从大到小选，遇到一个交叉空位即可
    for(auto p=x.begin(); p!=x.end(); p++){//枚举行
        for(auto q=v.rbegin(); q!=v.rend(); q++){//枚举列
            i = p->first, j = q->second;
            if(f.find(i*M+j) == f.end()){
                ans = max(ans, p->second+q->first);
                break;//空位，不需要减重复的，后面更小推出循环
            }//第二重循环总次数O(n)，因为每个元素只属于一行
            else{
                ans = max(ans, p->second+q->first-f[i*M+j]);
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}