QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #535229 | #8712. Flooding Wall | makrav# | 12 | 1688ms | 97648kb | C++20 | 7.3kb | 2024-08-27 21:53:28 | 2024-08-27 21:53:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define int ll
int pw2[500010];
struct node {
int len, pr, lolpr;
node() = default;
node(int l_, int pr_, int lolpr_) {
len = l_;
pr = pr_;
lolpr = lolpr_;
}
};
node operator+(node a, node b) {
if (a.len == -1) return b;
if (b.len == -1) return a;
int newlen = a.len + b.len;
int newpr = (a.pr * b.pr) % mod;
int newlol = (a.lolpr * b.pr + b.lolpr * pw2[a.len]) % mod;
return node(newlen, newpr, newlol);
}
struct segtree {
int n;
vector<node> t;
segtree() = default;
segtree(int n_) {
n = n_;
t.resize(4 * n);
build(1, 0, n);
}
void build(int v, int tl, int tr) {
if (tl + 1 == tr) {
t[v] = node(1, 0, 0);
return;
}
int tm = (tl + tr) / 2;
build(v * 2, tl, tm);
build(v * 2 + 1, tm, tr);
t[v] = t[v * 2] + t[v * 2 + 1];
}
void upd(int v, int tl, int tr, int p, int vl) {
if (tl + 1 == tr) {
t[v] = node(1, vl, vl);
return;
}
int tm = (tl + tr) / 2;
if (p < tm) upd(v * 2, tl, tm, p, vl);
else upd(v * 2 + 1, tm, tr, p, vl);
t[v] = t[v * 2] + t[v * 2 + 1];
}
node get(int v, int tl, int tr, int l, int r) {
if (tr <= l || tl >= r) return node(-1, -1, -1);
if (l <= tl && tr <= r) return t[v];
int tm = (tl + tr) / 2;
return get(v * 2, tl, tm, l, r) + get(v * 2 + 1, tm, tr, l, r);
}
};
void solve() {
int n; cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
int ans = 0;
for (int i = 0; i < n; i++) {
ans += (mod - ((a[i] + b[i]) * pw2[n - 1] % mod));
if (ans >= mod) ans -= mod;
}
{
vector<pair<int, int>> ev;
for (int i = 0; i < n; i++) {
ev.pb({a[i], -i});
ev.pb({b[i], -i});
}
sort(all(ev));
segtree sg(n);
vector<int> val(n, 0);
for (int i = 0; i < ev.size(); i++) {
int ind = -ev[i].second;
int prright = (ind == n - 1 ? 1 : sg.get(1, 0, n, ind + 1, n).pr);
if (!prright) {
val[ind]++;
sg.upd(1, 0, n, ind, val[ind]);
continue;
}
int LOL = (prright * pw2[ind]) % mod;
if (ind) {
node rs = sg.get(1, 0, n, 0, ind);
LOL += (((rs.lolpr + (mod - rs.pr) * rs.len) % mod) * prright) % mod;
LOL %= mod;
}
ans += LOL * ev[i].first;
ans %= mod;
//cout << ind << ' ' << ev[i].first << ' ' << LOL << " add to ans\n";
val[ind]++;
sg.upd(1, 0, n, ind, val[ind]);
}
for (int i = 0; i < n; i++) sg.upd(1, 0, n, i, 0);
val.assign(n, 0);
for (int I = 0; I < ev.size(); I++) {
int j = I;
while (j < ev.size() && ev[j].first == ev[I].first) j++;
//cout << I << ' ' << j << '\n';
vector<int> ps;
for (int k = I; k < j; k++) {
ps.pb(-ev[k].second);
val[ps.back()]++;
sg.upd(1, 0, n, ps.back(), val[ps.back()]);
}
reverse(all(ps));
vector<int> fuck_pref(ps.size() + 1), fuck_suff(ps.size() + 1);
int cp = 1, cpov = 1, cpv = 1;
vector<int> prs(ps.size() + 1, 1);
for (int i = 0; i < ps.size(); i++) {
int prv = (i == 0 ? 0 : ps[i - 1]);
if (ps[i] - prv >= 2) {
prs[i] = sg.get(1, 0, n, prv + 1, ps[i]).pr;
}
}
prs.back() = (ps.back() == n - 1 ? 1 : sg.get(1, 0, n, ps.back() + 1, n).pr);
for (int i = 0; i < ps.size(); i++) {
cp *= prs[i];
cp %= mod;
cpov *= (val[ps[i]] - 1); cpov %= mod;
cpv *= val[ps[i]];
cpv %= mod;
fuck_pref[i + 1] = (cp * (cpv + mod - cpov)) % mod;
}
cp = 1; cpov = 1; cpv = 1;
for (int i = ps.size() - 1; i >= 0; i--) {
cp *= prs[i + 1];
cp %= mod;
cpov *= (val[ps[i]] - 1); cpov %= mod;
cpv *= val[ps[i]];
cpv %= mod;
fuck_suff[ps.size() - i] = (cp * (cpv + mod - cpov)) % mod;
}
for (int i = 0; i < ps.size(); i++) {
int cnt_fuck1 = (ps[i] == 0 ? 1 : sg.get(1, 0, n, 0, ps[i]).pr) * (ps[i] == n - 1 ? 1 : sg.get(1, 0, n, ps[i] + 1, n).pr);
cnt_fuck1 %= mod;
int cnt_fuck2 = (((fuck_pref[i] * prs[i]) % mod) * ((fuck_suff[ps.size() - i - 1] * prs[i + 1]) % mod)) % mod * (val[ps[i]] - 1) % mod;
cnt_fuck2 += cnt_fuck1;
cnt_fuck2 %= mod;
//cout << ps[i] << ' ' << ev[I].first << ' ' << cnt_fuck2 << ' ' << cnt_fuck1 << '\n';
ans += (mod - (cnt_fuck2 * ev[I].first) % mod);
//cout << "minuss " << cnt_fuck2 * ev[I].first << '\n';
ans %= mod;
}
for (int i = 0; i < ps.size() - 1; i++) {
int lol = (((fuck_pref[i + 1] * fuck_suff[ps.size() - i - 1]) % mod * (ps[i + 1] - ps[i] - 1)) % mod * prs[i + 1] % mod) * ev[I].first % mod;
///cout << lol << '\n';
ans += mod - lol;
if (ans >= mod) ans -= mod;
}
I = j - 1;
}
}
reverse(all(a));
reverse(all(b));
{
//cout<<"didrev\n";
vector<pair<int, int>> ev;
for (int i = 0; i < n; i++) {
ev.pb({a[i], -i});
ev.pb({b[i], -i});
}
sort(all(ev));
segtree sg(n);
vector<int> val(n, 0);
for (int i = 0; i < ev.size(); i++) {
int ind = -ev[i].second;
int prright = (ind == n - 1 ? 1 : sg.get(1, 0, n, ind + 1, n).pr);
if (!prright) {
val[ind]++;
sg.upd(1, 0, n, ind, val[ind]);
continue;
}
int LOL = (prright * pw2[ind]) % mod;
if (ind) {
node rs = sg.get(1, 0, n, 0, ind);
LOL += (((rs.lolpr + (mod - rs.pr) * rs.len) % mod) * prright) % mod;
LOL %= mod;
}
ans += LOL * ev[i].first;
ans %= mod;
//cout << ind << ' ' << ev[i].first << ' ' << LOL << " add to ans\n";
val[ind]++;
sg.upd(1, 0, n, ind, val[ind]);
}
}
cout << ans << '\n';
}
signed main() {
pw2[0] = 1;
for (int i = 1; i < 500010; i++) pw2[i] = (pw2[i - 1] * 2) % mod;
int tt = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> tt;
#else
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#endif
while (tt--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 8
Accepted
time: 3ms
memory: 7496kb
input:
4 1 1 1 1 2 2 2 2
output:
6
result:
ok single line: '6'
Test #2:
score: 8
Accepted
time: 3ms
memory: 7792kb
input:
10 1 2 3 4 5 6 7 8 9 10 10 9 8 7 6 5 4 3 2 1
output:
21116
result:
ok single line: '21116'
Test #3:
score: 8
Accepted
time: 0ms
memory: 7548kb
input:
1 1 2
output:
0
result:
ok single line: '0'
Test #4:
score: 8
Accepted
time: 0ms
memory: 7492kb
input:
2 1 1 2 2
output:
0
result:
ok single line: '0'
Test #5:
score: 8
Accepted
time: 3ms
memory: 7488kb
input:
3 1 1 1 2 2 2
output:
1
result:
ok single line: '1'
Test #6:
score: 8
Accepted
time: 3ms
memory: 7488kb
input:
3 1 1 1 3 2 3
output:
3
result:
ok single line: '3'
Test #7:
score: 8
Accepted
time: 0ms
memory: 7508kb
input:
3 2 1 1 3 2 3
output:
4
result:
ok single line: '4'
Test #8:
score: 8
Accepted
time: 3ms
memory: 7492kb
input:
3 1 1 2 3 2 3
output:
4
result:
ok single line: '4'
Test #9:
score: 8
Accepted
time: 3ms
memory: 7784kb
input:
4 1 1 2 2 2 2 1 1
output:
6
result:
ok single line: '6'
Test #10:
score: 8
Accepted
time: 0ms
memory: 7784kb
input:
3 1 4 4 3 1 1
output:
2
result:
ok single line: '2'
Test #11:
score: 8
Accepted
time: 0ms
memory: 7764kb
input:
20 801072306 297281669 94099424 745640358 822582129 579751930 776707816 425952653 529794053 256263083 615445445 401366545 990263003 967996508 788867983 916880116 837997768 346996508 623409388 122077161 141734988 448434751 822901346 825591177 388082644 468025968 260356829 1164654 537396602 730502935 ...
output:
840988190
result:
ok single line: '840988190'
Test #12:
score: 8
Accepted
time: 0ms
memory: 7788kb
input:
15 792312195 195812430 401437979 703756992 502275277 612055402 556065888 470806179 556125857 640437896 240743729 861383776 500299988 911972088 161499505 167335533 694282920 379241393 144223073 973249939 83979787 962250505 359871412 130233016 655843497 928153117 542969567 974346871 369758881 962874102
output:
617169726
result:
ok single line: '617169726'
Test #13:
score: 8
Accepted
time: 3ms
memory: 7444kb
input:
20 1 1 2 1 1 1 2 2 2 2 2 1 1 1 1 2 2 1 2 1 2 2 1 2 2 2 1 1 1 1 1 2 2 2 2 1 1 2 1 2
output:
8388630
result:
ok single line: '8388630'
Test #14:
score: 8
Accepted
time: 3ms
memory: 7728kb
input:
15 2 1 1 2 1 2 2 1 2 1 2 1 2 2 1 1 2 2 1 2 1 1 2 1 2 1 2 1 1 2
output:
180241
result:
ok single line: '180241'
Test #15:
score: 8
Accepted
time: 3ms
memory: 7756kb
input:
20 10 3 8 2 5 7 8 3 3 10 5 6 1 2 1 9 10 2 7 10 6 6 2 3 6 10 4 6 7 2 3 3 5 7 2 8 2 1 5 1
output:
78020608
result:
ok single line: '78020608'
Test #16:
score: 0
Wrong Answer
time: 3ms
memory: 7496kb
input:
20 999999992 999999995 999999995 999999998 999999994 999999996 999999992 1000000000 1000000000 999999997 999999999 999999994 999999998 999999992 999999999 1000000000 999999993 999999999 999999996 999999998 999999998 999999998 999999996 999999993 999999996 999999997 1000000000 999999995 999999994 999...
output:
32686080
result:
wrong answer 1st lines differ - expected: '44474368', found: '32686080'
Subtask #2:
score: 0
Wrong Answer
Test #23:
score: 0
Wrong Answer
time: 0ms
memory: 7508kb
input:
100 948 425 211 688 416 81 356 602 712 954 117 522 797 75 281 491 662 669 78 156 939 526 929 937 916 619 166 777 48 898 449 278 298 714 668 755 679 38 389 602 195 135 672 833 655 541 473 27 596 274 351 353 598 993 837 246 950 99 179 751 481 843 550 195 964 279 806 82 330 599 124 756 649 838 513 625 ...
output:
683531851
result:
wrong answer 1st lines differ - expected: '164439470', found: '683531851'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 12
Accepted
Test #57:
score: 12
Accepted
time: 1682ms
memory: 97648kb
input:
500000 1 1 1 1 2 2 2 1 1 1 1 1 2 2 1 1 2 2 2 2 1 2 1 1 2 1 1 1 1 2 1 2 2 1 1 2 2 2 1 1 2 2 2 2 1 2 2 2 2 1 2 2 2 1 2 2 2 1 2 2 2 2 2 2 2 2 1 1 2 1 2 1 2 2 1 2 2 2 2 2 2 2 1 1 1 2 2 2 1 1 2 1 2 2 1 2 2 1 2 2 2 1 2 2 2 2 2 2 2 2 1 1 1 2 1 2 1 1 2 1 2 1 2 2 1 1 2 1 1 1 1 1 2 2 2 2 2 2 1 2 2 1 1 2 1 2 1...
output:
869044223
result:
ok single line: '869044223'
Test #58:
score: 12
Accepted
time: 1684ms
memory: 97348kb
input:
499993 1 1 2 1 1 2 1 1 2 1 1 1 2 2 2 2 1 1 1 2 1 1 1 2 2 2 1 1 2 2 1 2 1 2 1 2 1 2 2 2 2 1 1 2 1 2 1 2 2 1 1 2 2 2 2 2 1 1 2 1 1 2 1 1 2 2 2 1 2 2 1 2 1 1 2 1 1 2 1 1 1 1 2 1 1 1 2 2 1 1 2 1 1 1 2 2 2 2 1 1 2 1 2 1 2 2 1 2 1 1 1 1 2 1 1 2 1 2 2 1 2 2 2 2 2 1 2 2 1 1 1 2 1 1 1 1 2 1 1 1 2 1 1 2 1 1 1...
output:
480826834
result:
ok single line: '480826834'
Test #59:
score: 12
Accepted
time: 1674ms
memory: 97328kb
input:
500000 2 2 1 1 2 2 2 1 1 2 2 2 2 2 1 1 1 1 1 2 1 2 1 2 1 2 2 1 1 1 2 1 1 1 1 1 1 2 2 2 2 2 2 2 2 1 2 1 2 1 2 1 1 2 1 1 2 2 2 1 2 2 1 2 2 1 2 2 1 1 1 2 1 1 1 2 2 2 1 1 1 1 1 1 1 2 1 1 1 1 1 2 2 1 2 1 2 2 2 1 2 1 1 2 1 2 1 1 2 2 2 1 2 1 2 2 2 2 2 2 1 1 2 2 2 2 1 1 1 1 1 1 2 2 1 1 1 2 1 2 2 2 1 1 1 2 2...
output:
869044223
result:
ok single line: '869044223'
Test #60:
score: 12
Accepted
time: 1688ms
memory: 97320kb
input:
499999 2 1 2 2 1 2 1 1 2 1 1 1 2 2 2 1 1 2 2 2 1 1 1 2 2 2 2 2 1 2 2 1 1 2 2 2 2 1 1 2 1 2 2 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 2 2 2 2 2 1 2 1 2 1 2 1 2 1 1 1 1 1 1 2 1 1 1 1 2 1 2 2 1 1 2 2 1 2 1 1 2 1 2 1 1 2 1 1 1 2 2 1 1 2 2 2 2 2 1 2 1 2 2 1 1 1 2 2 1 1 2 1 1 2 1 1 1 2 1 2 1 1 2 1 2 1 2 1 2 2 2 1 1...
output:
192864306
result:
ok single line: '192864306'
Subtask #6:
score: 0
Skipped
Dependency #1:
0%