Submission #1005064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005064		emptypringlescan	Flooding Wall (BOI24_wall)	C++17	58 / 100	5048 ms	29864 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
long long twok[500005];
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	pair<long long,long long> 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<long long,int> > hei;
	for(int i=0; i<n; i++){
		if(arr[i].first>arr[i].second)swap(arr[i].first,arr[i].second);
		hei.push_back({arr[i].first,i});
		hei.push_back({arr[i].second,i});
	}
	sort(hei.begin(),hei.end(),greater<pair<long long,int> >());
	long long ans=0;
	int st[n],add1[n],add2[n];
	memset(add1,0,sizeof(add1));
	memset(add2,0,sizeof(add2));
	for(int i=0; i<n; i++) st[i]=2;
	for(auto [h,i]:hei){
		long long mult=1;
		for(int j=0; j<i; j++) mult=mult*st[j]%mod;
		for(int j=i+1; j<n; j++){
			if(h>arr[j].first){
				ans+=mult*add1[j]%mod*(h-arr[j].first)%mod;
			}
			if(h>arr[j].second){
				ans+=mult*add1[j]%mod*(h-arr[j].second)%mod;
			}
			add2[j]+=mult;
			if(add2[j]>=mod) add2[j]-=mod;
			mult=mult*st[j]%mod;
		}
		mult=1;
		for(int j=i+1; j<n; j++) mult=mult*st[j]%mod;
		for(int j=i-1; j>=0; j--){
			if(h>arr[j].first){
				ans+=mult*add2[j]%mod*(h-arr[j].first)%mod;
			}
			if(h>arr[j].second){
				ans+=mult*add2[j]%mod*(h-arr[j].second)%mod;
			}
			add1[j]+=mult;
			if(add1[j]>=mod) add1[j]-=mod;
			mult=mult*st[j]%mod;
		}
		st[i]--;
	}
	ans%=mod;
	cout << ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 17 / 17
• Subtask 3: 19 / 19
• Subtask 4: 14 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 30