結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 581 ms
28,596 KB
testcase_04 AC 560 ms
27,784 KB
testcase_05 AC 453 ms
23,680 KB
testcase_06 AC 692 ms
31,584 KB
testcase_07 AC 632 ms
30,432 KB
testcase_08 AC 705 ms
32,996 KB
testcase_09 AC 702 ms
32,972 KB
testcase_10 AC 367 ms
20,220 KB
testcase_11 AC 400 ms
20,480 KB
testcase_12 AC 564 ms
28,012 KB
testcase_13 AC 551 ms
27,240 KB
testcase_14 AC 764 ms
35,568 KB
testcase_15 AC 709 ms
32,768 KB
testcase_16 AC 601 ms
29,080 KB
testcase_17 AC 353 ms
19,676 KB
testcase_18 AC 431 ms
22,036 KB
testcase_19 AC 485 ms
25,260 KB
testcase_20 AC 498 ms
25,580 KB
testcase_21 AC 504 ms
25,564 KB
testcase_22 AC 460 ms
23,608 KB
testcase_23 AC 659 ms
31,540 KB
testcase_24 AC 464 ms
24,328 KB
testcase_25 AC 394 ms
21,368 KB
testcase_26 AC 398 ms
21,032 KB
testcase_27 AC 440 ms
23,108 KB
testcase_28 AC 716 ms
33,832 KB
testcase_29 AC 499 ms
25,436 KB
testcase_30 AC 703 ms
32,884 KB
testcase_31 AC 458 ms
23,848 KB
testcase_32 AC 476 ms
24,568 KB
testcase_33 AC 308 ms
36,088 KB
testcase_34 AC 321 ms
35,904 KB
testcase_35 AC 423 ms
35,896 KB
testcase_36 AC 425 ms
35,904 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define INF 1000000001LL
#define MOD 998244353LL
#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