結果

問題 No.1300 Sum of Inversions
ユーザー GGanariGGanari
提出日時 2024-05-24 11:12:38
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,049 bytes
コンパイル時間 2,814 ms
コンパイル使用メモリ 219,824 KB
実行使用メモリ 36,236 KB
最終ジャッジ日時 2024-05-24 11:13:02
合計ジャッジ時間 23,629 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 AC 326 ms
35,904 KB
testcase_34 AC 343 ms
36,112 KB
testcase_35 WA -
testcase_36 WA -
権限があれば一括ダウンロードができます

ソースコード

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)%MOD;
        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;
}
0