結果

問題 No.2950 Max Min Product
ユーザー 沙耶花沙耶花
提出日時 2024-10-25 21:46:29
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 943 ms / 3,000 ms
コード長 1,403 bytes
コンパイル時間 5,088 ms
コンパイル使用メモリ 278,704 KB
実行使用メモリ 20,728 KB
最終ジャッジ日時 2024-10-25 23:30:26
合計ジャッジ時間 32,314 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,820 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 621 ms
14,956 KB
testcase_04 AC 690 ms
16,632 KB
testcase_05 AC 647 ms
15,804 KB
testcase_06 AC 937 ms
18,424 KB
testcase_07 AC 939 ms
18,304 KB
testcase_08 AC 943 ms
17,660 KB
testcase_09 AC 387 ms
10,484 KB
testcase_10 AC 730 ms
15,936 KB
testcase_11 AC 619 ms
16,028 KB
testcase_12 AC 821 ms
17,652 KB
testcase_13 AC 833 ms
17,528 KB
testcase_14 AC 823 ms
17,696 KB
testcase_15 AC 793 ms
16,620 KB
testcase_16 AC 541 ms
16,224 KB
testcase_17 AC 615 ms
15,396 KB
testcase_18 AC 827 ms
16,476 KB
testcase_19 AC 822 ms
16,504 KB
testcase_20 AC 824 ms
16,344 KB
testcase_21 AC 492 ms
12,608 KB
testcase_22 AC 677 ms
16,472 KB
testcase_23 AC 448 ms
11,664 KB
testcase_24 AC 925 ms
19,624 KB
testcase_25 AC 925 ms
20,728 KB
testcase_26 AC 926 ms
20,628 KB
testcase_27 AC 516 ms
15,136 KB
testcase_28 AC 829 ms
18,152 KB
testcase_29 AC 591 ms
15,000 KB
testcase_30 AC 776 ms
16,524 KB
testcase_31 AC 850 ms
17,480 KB
testcase_32 AC 824 ms
16,672 KB
testcase_33 AC 483 ms
15,512 KB
testcase_34 AC 318 ms
9,816 KB
testcase_35 AC 466 ms
15,892 KB
testcase_36 AC 669 ms
17,264 KB
testcase_37 AC 672 ms
16,632 KB
testcase_38 AC 668 ms
16,436 KB
testcase_39 AC 2 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000001
#define Inf64 1000000000000000000LL
vector<int> a;
mint ans = 0;

void dfs(int l,int r){
	if(l==r)return;
	if(r-l==1){
		ans += mint(a[l]).pow(2);
		return;
	}
	int m = (l+r)/2;
	dfs(l,m);
	dfs(m+1,r);
	vector<vector<int>> t;
	vector<int> ms;
	{
		int mini = Inf32,maxi = -Inf32;
		for(int i=m;i<r;i++){
			mini = min(mini,a[i]);
			maxi = max(maxi,a[i]);
			t.push_back({mini,maxi,1});
			ms.push_back(maxi);
		}
	}
	{
		int mini = Inf32,maxi = -Inf32;
		t.push_back({mini,maxi,0});
		ms.push_back(maxi);
		for(int i=m-1;i>=l;i--){
			mini = min(mini,a[i]);
			maxi = max(maxi,a[i]);
			t.push_back({mini,maxi,0});
			ms.push_back(maxi);
		}
	}
	sort(ms.begin(),ms.end());
	ms.erase(unique(ms.begin(),ms.end()),ms.end());
	sort(t.rbegin(),t.rend());
	vector fc(2,fenwick_tree<mint>(ms.size()));
	auto fs = fc;
	rep(i,t.size()){
		int pos = lower_bound(ms.begin(),ms.end(),t[i][1])-ms.begin();
		mint tt = fs[t[i][2]^1].sum(pos,ms.size());
		tt += fc[t[i][2]^1].sum(0,pos)*t[i][1];
		tt *= t[i][0];
		ans += tt;
		fc[t[i][2]].add(pos,1);
		fs[t[i][2]].add(pos,t[i][1]);
	}
}

int main(){
	int n;
	cin>>n;
	a.resize(n);
	rep(i,n) cin>>a[i];
	dfs(0,n);
	cout<<ans.val()<<endl;
	return 0;
}
0