Submission #1004914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004914		pavement	Flooding Wall (BOI24_wall)	C++17	56 / 100	5080 ms	42704 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], prf_ft[1500005], suf_ft[1500005];
vector<int> disc_vec;
multiset<int> prf_a, suf_a;

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 get_disc(int x) {
	return lower_bound(disc_vec.begin(), disc_vec.end(), x) - disc_vec.begin() + 1;
}

int ls(int x) {
	return x & -x;
}

int ft_qry(int ft[], int p) {
	int r = 0;
	for (; p; p -= ls(p)) {
		r += ft[p];
	}
	return r;
}

void ft_upd(int ft[], int p, int v) {
	for (; p <= (int)disc_vec.size(); p += ls(p)) {
		ft[p] += v;
	}
}

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 delta = -1; delta <= 1; delta++) {
			disc_vec.pb(a[i] + delta);
			disc_vec.pb(b[i] + delta);
		}
		suf_a.insert(a[i]);
	}
	sort(disc_vec.begin(), disc_vec.end());
	disc_vec.erase(unique(disc_vec.begin(), disc_vec.end()), disc_vec.end());
	for (int i = 1; i <= N; i++) {
		ft_upd(suf_ft, get_disc(b[i]), 1);
	}
	for (int i = 1; i <= N; i++) {
		ft_upd(suf_ft, get_disc(b[i]), -1);
		suf_a.erase(suf_a.find(a[i]));
		int max_prf_a = (prf_a.empty() ? 0 : *prf_a.rbegin());
		int max_suf_a = (suf_a.empty() ? 0 : *suf_a.rbegin());
		for (int h : {a[i], b[i]}) {
			int expected = 0;
			vector<int> probs = {1}, vals = {h};
			for (auto it = upper_bound(disc_vec.begin(), disc_vec.end(), h); it != disc_vec.end(); ++it) {
				int v = *it;
				int lft_prob = 1, rig_prob = 1;
				if (max_prf_a >= v) {
					lft_prob = 0;
				} else {
					int cnt_small = ft_qry(prf_ft, it - disc_vec.begin());
					int oth = i - 1 - cnt_small;
					lft_prob = exp_mod(INV_2, oth);
				}
				lft_prob = (1 - lft_prob + MOD) % MOD;
				if (max_suf_a >= v) {
					rig_prob = 0;
				} else {
					int cnt_small = ft_qry(suf_ft, it - disc_vec.begin());
					int oth = (N - i) - cnt_small;
					rig_prob = exp_mod(INV_2, oth);
				}
				rig_prob = (1 - rig_prob + MOD) % MOD;
				int p = (ll)lft_prob * rig_prob % MOD;
				probs.pb(p);
				vals.pb(v);
			}
			for (int idx = 0; idx + 1 < (int)probs.size(); idx++) {
				int tmp = (probs[idx] - probs[idx + 1] + MOD) % MOD;
				expected = (expected + (ll)vals[idx] * tmp % MOD) % MOD;
			}
			expected = (expected - h + MOD) % MOD;
			glob = (glob + expected) % MOD;
		}
		ft_upd(prf_ft, get_disc(b[i]), 1);
		prf_a.insert(a[i]);
	}
	for (int rep = 0; rep < N - 1; rep++) {
		glob = (glob * 2) % MOD;
	}
	cout << glob << '\n';
}

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