Submission #1004919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004919		pavement	Flooding Wall (BOI24_wall)	C++17	17 / 100	5097 ms	2652 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define pb push_back

const int MOD = (int)1e9 + 7, INV_2 = (MOD + 1) / 2;
int N, glob, a[500005], b[500005];

int exp_mod(int a, int b) {
	int r = 1;
	while (b) {
		if (b % 2 == 1) {
			r = (ll)r * a % MOD;
		}
		a = (ll)a * a % MOD;
		b /= 2;
	}
	return r;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= N; i++) {
		cin >> b[i];
		if (a[i] > b[i]) {
			swap(a[i], b[i]);
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int h : {a[i], b[i]}) {
			int max_p_a = 0, max_s_a = 0;
			for (int j = 1; j < i; j++) {
				max_p_a = max(max_p_a, a[j]);
			}
			for (int j = i + 1; j <= N; j++) {
				max_s_a = max(max_s_a, a[j]);
			}
			if (max_p_a <= max_s_a) {
				glob = (glob + max(0, max_p_a - h)) % MOD;
				for (int v = max(h, max_p_a) + 1; v <= max_s_a; v++) {
					int cnt_lft_b = 0;
					for (int j = 1; j < i; j++) {
						if (b[j] >= v) {
							cnt_lft_b++;
						}
					}
					int cur = (1 - exp_mod(INV_2, cnt_lft_b) + MOD) % MOD;
					glob = (glob + cur) % MOD;
				}
				for (int v = max(h, max_s_a) + 1; v <= 1001; v++) {
					int cnt_rig_b = 0;
					int cnt_lft_b = 0;
					for (int j = 1; j < i; j++) {
						if (b[j] >= v) {
							cnt_lft_b++;
						}
					}
					for (int j = i + 1; j <= N; j++) {
						if (b[j] >= v) {
							cnt_rig_b++;
						}
					}
					int tmp = ((exp_mod(INV_2, cnt_lft_b + cnt_rig_b) - exp_mod(INV_2, cnt_rig_b) + MOD) % MOD - exp_mod(INV_2, cnt_lft_b) + MOD) % MOD;
					tmp = (1 + tmp) % MOD;
					glob = (glob + tmp) % MOD;
				}
			} else {
				glob = (glob + max(0, max_s_a - h)) % MOD;
				for (int v = max(h, max_s_a) + 1; v <= max_p_a; v++) {
					int cnt_rig_b = 0;
					for (int j = i + 1; j <= N; j++) {
						if (b[j] >= v) {
							cnt_rig_b++;
						}
					}
					int cur = (1 - exp_mod(INV_2, cnt_rig_b) + MOD) % MOD;
					glob = (glob + cur) % MOD;
					
				}
				for (int v = max(h, max_p_a) + 1; v <= 1001; v++) {
					int cnt_rig_b = 0;
					int cnt_lft_b = 0;
					for (int j = 1; j < i; j++) {
						if (b[j] >= v) {
							cnt_lft_b++;
						}
					}
					for (int j = i + 1; j <= N; j++) {
						if (b[j] >= v) {
							cnt_rig_b++;
						}
					}
					int tmp = ((exp_mod(INV_2, cnt_lft_b + cnt_rig_b) - exp_mod(INV_2, cnt_rig_b) + MOD) % MOD - exp_mod(INV_2, cnt_lft_b) + MOD) % MOD;
					tmp = (1 + tmp) % MOD;
					glob = (glob + tmp) % MOD;
				}
			}
		}
	}
	for (int rep = 0; rep < N - 1; rep++) {
		glob = (glob * 2) % MOD;
	}
	cout << glob << '\n';
}

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