数据本地能过,洛谷RE
查看原帖
数据本地能过,洛谷RE
833124
BIOS楼主2023/12/23 13:45

RT,第一组数据下完在本地能过,去别的地方的在线IDE也能过,到洛谷全紫

#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
const int N = 5e4 + 5, lim = 5e4;
int tr1[N], tr2[N], n, res, tmp;
struct node
{
    int v, x;
} cow[N];
bool cmp(node a, node b) { return a.v == b.v ? a.x < b.x : a.v < b.v; }
int lowbit(int x) { return x & -x; }
int sum(int tr[], int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += tr[i];
    return res;
}
int add(int tr[], int x, int v)
{
    for (int i = x; i <= lim; i += lowbit(i))
        tr[i] += v;
}
signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> cow[i].v >> cow[i].x;
    sort(cow + 1, cow + n + 1, cmp);
    for (int i = 1; i <= n; i++)
    {
        add(tr1, cow[i].x, 1), add(tr2, cow[i].x, cow[i].x);
        res += (cow[i].x * sum(tr1, cow[i].x - 1) - sum(tr2, cow[i].x - 1)) * cow[i].v;
        tmp = sum(tr2, lim) - sum(tr2, cow[i].x);
        tmp -= cow[i].x * (sum(tr1, lim) - sum(tr1, cow[i].x));
        res += cow[i].v * tmp;
    }
    cout << res << "\n";
}
2023/12/23 13:45
加载中...