萌新初学归并惨被干碎心灰意冷求大佬调代码
查看原帖
萌新初学归并惨被干碎心灰意冷求大佬调代码
1149429
FlamingBlade楼主2023/12/25 17:48
//start time: 5:08
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4 + 5;
inline int read(){
    int s = 0,f = 1;char c = getchar();
    while (!isdigit(c)){if (c == '-')f = -1;c = getchar();}
    while (isdigit(c)){s = (s<<3) + (s<<1) + (c ^ 48);c = getchar();}
    return s * f;
}
int n,sum[N],ans;
struct node{
    int val,dis;
    friend bool operator < (const node x,const node y){
        return x.val < y.val;
    }
}a[N],b[N];
void solve(int l,int r){
    if (l >= r) return;
    int mid = l + r >> 1;
    solve(l,mid);solve(mid + 1,r);
    int L = l,tar = 0;
    for (int i = l;i <= mid;i++) sum[i] = sum[i - 1] + a[i].dis;
    for (int R = mid + 1;R <= r;R++){
        while (L <= mid && a[L].dis <= a[R].dis){b[++tar] = a[L++];}
        ans += a[R].val * ((L - l) * a[R].dis - (sum[L - 1] - sum[l - 1]) 
        + sum[mid] - sum[L - 1] - (mid - L + 1) * a[R].dis);
        b[++tar] = a[R];
    }
    for (int i = l;i <= r;i++) a[i] = b[i - l + 1];
}
signed main(){
    n = read();
    for (int i = 1;i <= n;i++) a[i] = (node){read(),read()};
    sort(a + 1,a + n + 1);
    solve(1,n);
    cout << ans << endl;
    return 0;
}
2023/12/25 17:48
加载中...