Submission #1140132

#TimeUsernameProblemLanguageResultExecution timeMemory
1140132AbdullahIshfaqFlooding Wall (BOI24_wall)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 998244353
void solve(){
	int n;
	cin >> n;
	pair<ll,ll> arr[n];
	for(int i = 0; i < n; i++){
		cin >> arr[i].first;
	}
	for(int i = 0; i < n; i++){
		cin >> arr[i].second;
	}
	vector<pair<ll,ll>> rngs;
	for(int i = 0; i < n; i++){
		if(arr[i].first > arr[i].second){
			swap(arr[i].first, arr[i].second);
		}
		rngs.push_back({arr[i].first, i});
		rngs.push_back({arr[i].second, i});
	}
	sort(rngs.rbegin(), rngs.rend());
	ll ans = 0;
	int st[n], add1[n] = {}, add2[n] = {};
	for(int i = 0; i < n; i++){
		st[i] = 2;
	}
	for(auto [h, i] : rngs){
		ll res = 1;
		for(int j = 0; j < i; j++){
			res = res * st[j] % MOD;
		}
		for(int j = i + 1; j < n; j++){
			if(h > arr[j].first){
				ans += res * add1[j] % MOD *(h - arr[j].first) % MOD;
			}
			if(h > arr[j].second){
				ans += res * add1[j] % MOD *(h - arr[j].second) % MOD;
			}
			add2[j] += res;
			add2[j] %= MOD;
			res = (res * st[j]) % MOD;
		}
		res = 1;
		for(int j = i + 1; j < n; j++){
			res = res * st[j] % MOD;
		}
		for(int j = i - 1; j >= 0; j--){
			if(h > arr[j].first){
				ans += res * add2[j] % MOD * (h - arr[j].first)%MOD;
			}
			if(h > arr[j].second){
				ans += res * add2[j] % MOD * (h - arr[j].second)%MOD;
			}
			add1[j] += res;
			add1[j] %= MOD;
			res = (res * st[j])%MOD;
		}
		st[i]--;
	}
	cout << ans % MOD << '\n';
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int tests = 1;
	// cin >> tests;
	for(int i = 1; i <= tests; i++){
		solve();
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...