結果

問題 No.1300 Sum of Inversions
ユーザー GGanari
提出日時 2024-05-24 11:08:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,043 bytes
コンパイル時間 2,613 ms
コンパイル使用メモリ 211,328 KB
最終ジャッジ日時 2025-02-21 16:34:10
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 WA * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#define INF 1000000001LL
#define MOD 1000000007LL
#define long long long
#define all(x) x.begin(),x.end()
using namespace std;
struct Node
{
    long value = 0;
};
class SegTree
{
private:
    vector<Node> arr;
    vector<Node> tree;
    int n;
    Node trash = {0}; //의미없는 값 입력
    Node merge(Node a, Node b)
    {
        //여기를 커스텀 구현
        Node res;
        res.value = a.value+b.value;
        return res;
    }
    Node init(int node, int start, int end)
    {
        if(start == end)
            return tree[node] = arr[start];
        int mid = (start+end)/2;
        return tree[node] = merge(init(node*2,start,mid),init(node*2+1,mid+1,end));
    }
    Node query(int node, int start, int end, int left, int right)
    {
        if(start > right || end < left)
            return trash;
        if(start >= left && end <= right)
            return tree[node];
        
        int mid = (start+end)/2;
        return merge(query(node*2,start,mid,left,right),query(node*2+1,mid+1,end,left,right));
    }
    Node update(int node, int start, int end, int index, long l)
    {
        if(start > index || end < index)
            return tree[node];
        if(start == end)
        {
            tree[node].value+=l;
            return tree[node];
        }
        int mid = (start+end)/2;
        return tree[node]=merge(update(node*2,start,mid,index,l),update(node*2+1,mid+1,end,index,l));
    }
public:
    void init(int l)
    {
        n = l;
        arr = vector<Node>(n);
        tree = vector<Node>(4*n);
    }
    void init(vector<Node> a)
    {
        n = a.size();
        arr = a;
        tree = vector<Node>(4*n);
        init(1,0,n-1);
    }
    void init(vector<long> a)
    {
        n = a.size();
        arr = vector<Node>(n);
        for(int i = 0; i<n; i++)
            arr[i].value = a[i];
        tree = vector<Node>(4*n);
        init(1,0,n-1);
    }
    long query(int left, int right)
    {
        if(left > right)
            return 0;
        return query(1,0,n-1,left,right).value%MOD;
    }
    void update(int index, long val)
    {
        update(1,0,n-1,index,val);
    }
};
int main()
{
    ios_base::sync_with_stdio(0); 
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> arr(n);
    vector<int> sortArr(n);
    for(int i = 0; i<n; i++)
    {
        cin >> arr[i];
        sortArr[i] = arr[i];
    }
    sort(all(sortArr));
    SegTree hapL;
    hapL.init(n);
    SegTree cntL;
    cntL.init(n);
    SegTree hapR;
    hapR.init(n);
    SegTree cntR;
    cntR.init(n);
    for(int i = 0; i<n; i++)
    {
        int v = lower_bound(all(sortArr),arr[i])-sortArr.begin();
        hapR.update(v,arr[i]);
        cntR.update(v,1);
    }
    long res = 0;
    for(int i = 0; i<n; i++)
    {
        int v = lower_bound(all(sortArr),arr[i])-sortArr.begin();
        hapR.update(v,-arr[i]);
        cntR.update(v,-1);
        long l = (hapL.query(v+1,n-1)*cntR.query(0,v-1))%MOD;
        long r = hapR.query(0,v-1)*cntL.query(v+1,n-1)%MOD;
        res+=l+r+(cntR.query(0,v-1)*cntL.query(v+1,n-1)%MOD)*arr[i];
        res%=MOD;
        cntL.update(v,1);
        hapL.update(v,arr[i]);
    }
    cout << res << endl;
    
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0