Submission #1004919

#TimeUsernameProblemLanguageResultExecution timeMemory
1004919pavementFlooding Wall (BOI24_wall)C++17
17 / 100
5097 ms2652 KiB
#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'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...