Submission #1215078

#TimeUsernameProblemLanguageResultExecution timeMemory
1215078stefanneaguFlooding Wall (BOI24_wall)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int nmax = 1e5 + 1, mod = 1e9 + 7; struct str { int a, b; } v[nmax]; vector<pair<int, int>> bag; int pref[nmax][2]; int suf[nmax][2]; int pw[nmax]; bool f[nmax]; /* int p2[nmax]; int i2[nmax]; int fast(int N, int E) { int ans = 1; while (E) { if (E & 1) { ans = (ans * N) % mod; } N = (N * N) % mod; } return ans; } void pre() { p2[0] = 1; for (int i = 1; i < nmax; i++) { p2[i] = (2 * p2[i - 1]) % mod; } i2[nmax - 1] = fast(p2[nmax - 1], mod - 2); for (int i = nmax - 2; i >= 0; i--) { i2 = (2 * i2[i + 1]) % mod; } } */ void pwb(int n) { for (int i = 1; i <= n; i++) { pw[i] = 2; } } int32_t main() { // pre(); ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> v[i].a; } for (int i = 1; i <= n; i++) { cin >> v[i].b; if (v[i].a < v[i].b) { swap(v[i].a, v[i].b); } bag.push_back({v[i].a, i}); bag.push_back({v[i].b, i}); } sort(bag.begin(), bag.end(), greater<pair<int, int>>()); pwb(n); int ind = 0; while (ind < bag.size()) { vector<pair<int, int>> cr; cr.push_back(bag[ind++]); while (ind < bag.size() && cr.back().first == bag[ind].first) { cr.push_back(bag[ind++]); } for (auto [nr, i] : cr) { pref[i][f[i]] = 1; for (int j = i - 1; j >= 1; j--) { pref[i][f[i]] = (pref[i][f[i]] * pw[j]) % mod; } suf[i][f[i]] = 1; for (int j = i + 1; j <= n; j++) { suf[i][f[i]] = (suf[i][f[i]] * pw[j]); } f[i] = 1; } for (auto [nr, i] : cr) { pw[i]--; } } sort(bag.begin(), bag.end()); int ans = 0; pwb(n); ind = 0; for (auto [nr, i] : bag) { // negativ int sp = 0, ss = 0; int prod = 1; for (int j = i - 1; j >= 1; j--) { if (v[j].a >= nr) { sp = (sp + prod * pref[j][0]) % mod; } if (v[j].b >= nr) { sp = (sp + prod * pref[j][1]) % mod; } prod = (prod * pw[j]) % mod; } prod = 1; for (int j = i + 1; j <= n; j++) { if (i == 1) { cout << i << " " << j << ": " << prod * suf[j][0] << " " << prod * suf[j][0] << '\n'; } if (v[j].a >= nr) { ss = (ss + prod * suf[j][0]) % mod; } if (v[j].b >= nr) { ss = (ss + prod * suf[j][1]) % mod; } prod = (prod * pw[j]) % mod; } pw[i]--; ans -= (ss * sp) * nr; cout << i << ": " << ss << " " << sp << '\n'; // cout << "?? " << i << ": " << ss * sp << '\n'; } cout << "\n\n\n"; pwb(n); for (int i = 1; i <= n; i++) { f[i] = 0; } sort(bag.begin(), bag.end(), greater<pair<int, int>>()); for (auto [nr, i] : bag) { // pozitiv int sp = 0; int prod = pw[i - 1]; for (int j = i - 2; j >= 1; j--) { if (v[j].a >= nr) { sp = (sp + prod * pref[j][0] * (i - j - 1)) % mod; } if (v[j].b >= nr) { sp = (sp + prod * pref[j][1] * (i - j - 1)) % mod; } prod = (prod * pw[j]) % mod; } int ss = 0; prod = pw[i + 1]; for (int j = i + 2; j <= n; j++) { if (v[j].a > nr) { ss = (ss + prod * suf[j][0] * (j - i - 1)) % mod; } if (v[j].b > nr) { ss = (ss + prod * suf[j][1] * (j - i - 1)) % mod; } prod = (prod * pw[j]) % mod; } ans += (ss * pref[i][f[i]] + sp * suf[i][f[i]]) * nr; cout << i << ": " << ss << " " << sp << '\n'; f[i] = 1; pw[i]--; } cout << ans; return 0; }
#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...