QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#416852 | #8712. Flooding Wall | zhoukangyang# | 12 | 123ms | 26984kb | C++14 | 2.9kb | 2024-05-22 09:50:43 | 2024-05-22 09:50:43 |
Judging History
answer
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define sz(a) ((int) (a).size())
#define vi vector < int >
#define me(a, x) memset(a, x, sizeof(a))
#define ull unsigned long long
#define ld __float128
#define pb emplace_back
using namespace std;
const int N = 1 << 21, mod = 1e9 + 7;
int n;
int a[N], b[N];
int arr[N], tot;
int sum1[N], sum2[N], tag[N];
void adt(int x, int w) {
sum1[x] = (ll)sum1[x] * w % mod;
sum2[x] = (ll)sum2[x] * w % mod;
tag[x] = (ll)tag[x] * w % mod;
}
void push(int x) {
if(tag[x] != 1) adt(x * 2, tag[x]), adt(x * 2 + 1, tag[x]), tag[x] = 1;
}
void upd(int x) {
sum1[x] = (sum1[x * 2] + sum1[x * 2 + 1]) % mod;
sum2[x] = (sum2[x * 2] + sum2[x * 2 + 1]) % mod;
}
inline void add(int x, int L, int R, int l, int r, int w) {
// if(l <= L && R <= r)
if(L==R) return adt(x, w), void();
int mid = (L + R) >> 1;
push(x);
if(l <= mid) add(x * 2, L, mid, l, r, w);
if(r > mid) add(x * 2 + 1, mid + 1, R, l, r, w);
upd(x);
}
inline int query(int x, int L, int R, int l, int r) {
// if(l <= L && R <= r)
if(L==R) return sum1[x];
push(x);
int mid = (L + R) >> 1, ret = 0;
if(l <= mid) ret += query(x * 2, L, mid, l, r);
if(r > mid) ret += query(x * 2 + 1, mid + 1, R, l, r);
return ret % mod;
}
void inc(int x, int L, int R, int p, int w) {
if(L == R) return (sum1[x] += w) %= mod, (sum2[x] += (ll)w * arr[p] % mod) %= mod, void();
push(x); int mid = (L + R) >> 1; p <= mid ? inc(x * 2, L, mid, p, w) : inc(x * 2 + 1, mid + 1, R, p, w); upd(x);
}
void build(int x, int L, int R) {
tag[x] = 1;
if(L == R) return sum1[x] = sum2[x] = (L == 1), void();
int mid = (L + R) >> 1;
build(x * 2, L, mid), build(x * 2 + 1, mid + 1, R), upd(x);
}
int pw[N];
int main() {
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
L(i, 1, n) {
cin >> a[i];
}
L(i, 1, n) {
cin >> b[i];
}
L(i, 1, n) {
arr[++tot] = a[i];
arr[++tot] = b[i];
}
sort(arr + 1, arr + tot + 1);
tot = unique(arr + 1, arr + tot + 1) - arr - 1;
L(i, 1, n) {
a[i] = lower_bound(arr + 1, arr + tot + 1, a[i]) - arr;
b[i] = lower_bound(arr + 1, arr + tot + 1, b[i]) - arr;
}
pw[0] = 1;
L(i, 1, n) {
pw[i] = (ll)pw[i - 1] * 2 % mod;
}
int ans = 0;
L(tst, 0, 1) {
build(1, 1, tot);
L(i, 1, n) {
if(a[i] > b[i])swap(a[i], b[i]);
int d = query(1, 1, tot, 1, a[i]);
add(1, 1, tot, 1, a[i], 0);
inc(1, 1, tot, a[i], d);
int s = query(1, 1, tot, 1, b[i]);
inc(1, 1, tot, b[i], s);
if(b[i] < tot) add(1, 1, tot, b[i] + 1, tot, 2);
(ans += (ll) sum2[1] * pw[n - i] % mod) %= mod;
}
if(tst == 1) {
(ans += mod - (ll) n * sum2[1] % mod) %= mod;
}
reverse(b + 1, b + tot + 1);
reverse(a + 1, a + tot + 1);
}
L(i, 1, n) {
(ans += mod - (ll) (arr[a[i]] + arr[b[i]]) * pw[n - 1] % mod) %= mod;
}
cout << ans << '\n';
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: 0ms
memory: 13732kb
input:
4 1 1 1 1 2 2 2 2
output:
6
result:
ok single line: '6'
Test #2:
score: 8
Accepted
time: 2ms
memory: 13884kb
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: 2ms
memory: 13824kb
input:
1 1 2
output:
0
result:
ok single line: '0'
Test #4:
score: 8
Accepted
time: 0ms
memory: 13828kb
input:
2 1 1 2 2
output:
0
result:
ok single line: '0'
Test #5:
score: 8
Accepted
time: 2ms
memory: 13768kb
input:
3 1 1 1 2 2 2
output:
1
result:
ok single line: '1'
Test #6:
score: 8
Accepted
time: 0ms
memory: 13860kb
input:
3 1 1 1 3 2 3
output:
3
result:
ok single line: '3'
Test #7:
score: 8
Accepted
time: 2ms
memory: 13764kb
input:
3 2 1 1 3 2 3
output:
4
result:
ok single line: '4'
Test #8:
score: 8
Accepted
time: 0ms
memory: 13764kb
input:
3 1 1 2 3 2 3
output:
4
result:
ok single line: '4'
Test #9:
score: 8
Accepted
time: 0ms
memory: 13824kb
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: 13776kb
input:
3 1 4 4 3 1 1
output:
2
result:
ok single line: '2'
Test #11:
score: 0
Wrong Answer
time: 2ms
memory: 13776kb
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:
438202902
result:
wrong answer 1st lines differ - expected: '840988190', found: '438202902'
Subtask #2:
score: 0
Wrong Answer
Test #23:
score: 0
Wrong Answer
time: 0ms
memory: 13740kb
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:
834010737
result:
wrong answer 1st lines differ - expected: '164439470', found: '834010737'
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: 119ms
memory: 26080kb
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: 121ms
memory: 24280kb
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: 123ms
memory: 26628kb
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: 123ms
memory: 26984kb
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%