oj.uz

답안 #1004924

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1004924 2024-06-22T04:20:36 Z pavement Flooding Wall (BOI24_wall) C++17
0 / 100
 5000 ms 2520 KB 
#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;
}

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

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, (int)1e9, 1);
	root[1] = new node(1, (int)1e9, exp_mod(INV_2, N));
	for (int i = 1; i <= N; i++) {
		root[1]->mul(1, b[i], 2);
		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;
				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, max_s_a) + MOD) % 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;
				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, max_p_a) + MOD) % 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;
				}
			}
		}
		root[0]->mul(1, b[i], INV_2);
	}
	for (int rep = 0; rep < N - 1; rep++) {
		glob = (glob * 2) % MOD;
	}
	cout << glob << '\n';
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2516 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Incorrect 0 ms 2396 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2520 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Incorrect 1 ms 2392 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2520 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Incorrect 1 ms 2392 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2516 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Incorrect 0 ms 2396 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 12 ms 2392 KB Output is correct
9 Correct 11 ms 2396 KB Output is correct
10 Execution timed out 5096 ms 2396 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2516 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Incorrect 0 ms 2396 KB Output isn't correct
12 Halted 0 ms 0 KB -