Submission #1004936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004936		pavement	Flooding Wall (BOI24_wall)	C++17	100 / 100	3565 ms	941856 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, LIM = (int)1e9;
int N, glob, a[500005], b[500005], pf_a[500005], sf_a[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;
}

struct node {
	node *left, *right;
	int val, pv;
	node(const int &_s, const int &_e) : left(nullptr), right(nullptr), val(_e - _s + 1), pv(1) {}
	void cc(const int &S, const int &E) {
		if (left == nullptr) {
			int M = (S + E) / 2;
			left = new node(S, M);
			right = new node(M + 1, E);
		}
	}
	void prop(const int &S, const int &E) {
		cc(S, E);
		if (pv == 1) {
			return;
		}
		left->val = ((ll)left->val * pv) % MOD;
		left->pv = ((ll)left->pv * pv) % MOD;
		right->val = ((ll)right->val * pv) % MOD;
		right->pv = ((ll)right->pv * pv) % MOD;
		pv = 1;
	}
	void mul(int l, int r, int v, int S = 1, int E = LIM + 1) {
		if (l > E || r < S) {
			return;
		}
		if (l <= S && E <= r) {
			val = ((ll)val * v) % MOD;
			pv = ((ll)pv * v) % MOD;
			return;
		}
		prop(S, E);
		int M = (S + E) / 2;
		left->mul(l, r, v, S, M);
		right->mul(l, r, v, M + 1, E);
		val = (left->val + right->val) % MOD;
	}
	int sum(int l, int r, int S = 1, int E = LIM + 1) {
		if (l > E || r < S) {
			return 0;
		}
		if (l <= S && E <= r) {
			return val;
		}
		prop(S, E);
		int M = (S + E) / 2;
		return (left->sum(l, r, S, M) + right->sum(l, r, M + 1, E)) % MOD;
	}
} *root[3];

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]);
		}
	}
	root[0] = new node(1, LIM + 1);
	root[1] = new node(1, LIM + 1);
	root[2] = new node(1, LIM + 1);
	for (int i = 1; i <= N; i++) {
		root[1]->mul(1, b[i], INV_2);
		root[2]->mul(1, b[i], INV_2);
		pf_a[i] = max(a[i], pf_a[i - 1]);
	}
	for (int i = N; i >= 1; i--) {
		sf_a[i] = max(a[i], sf_a[i + 1]);
	}
	for (int i = 1; i <= N; i++) {
		root[1]->mul(1, b[i], 2);
		root[2]->mul(1, b[i], 2);
		for (int h : {a[i], b[i]}) {
			int max_p_a = pf_a[i - 1], max_s_a = sf_a[i + 1];
			if (max_p_a <= max_s_a) {
				glob = (glob + max(0, max_p_a - h)) % MOD;
				glob = (glob + max(0, max_s_a - (max(h, max_p_a) + 1) + 1)) % MOD;
				glob = (glob - root[0]->sum(max(h, max_p_a) + 1, LIM + 1) + MOD) % MOD;
				
				glob = (glob + max(0, LIM + 1 - (max(h, max_s_a) + 1) + 1)) % MOD;
				glob = (glob - root[1]->sum(max(h, max_s_a) + 1, LIM + 1) + MOD) % MOD;
				
				glob = (glob + root[2]->sum(max(h, max_s_a) + 1, LIM + 1)) % MOD;
			} else {
				glob = (glob + max(0, max_s_a - h)) % MOD;
				glob = (glob + max(0, max_p_a - (max(h, max_s_a) + 1) + 1)) % MOD;
				glob = (glob - root[1]->sum(max(h, max_s_a) + 1, LIM + 1) + MOD) % MOD;
				
				glob = (glob + max(0, LIM + 1 - (max(h, max_p_a) + 1) + 1)) % MOD;
				glob = (glob - root[0]->sum(max(h, max_p_a) + 1, LIM + 1) + MOD) % MOD;
				
				glob = (glob + root[2]->sum(max(h, max_p_a) + 1, LIM + 1)) % MOD;
			}
		}
		root[0]->mul(1, b[i], INV_2);
		root[2]->mul(1, b[i], INV_2);
	}
	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: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 30 / 30