QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#74238 | #5433. Absolute Difference | XKError | WA | 2ms | 4156kb | C++14 | 2.8kb | 2023-01-31 10:24:38 | 2023-01-31 10:24:40 |
Judging History
answer
#include <bits/stdc++.h>
#define maxn 200005
#define db double
#define int long long
using namespace std;
int n, m;
struct node{
int l, r;
db prb;
node () {}
node (int x, int y, db z = 0) {
l = x, r = y, prb = z;
}
int len() {
return r - l;
}
db mid() {
return (l + r) / 2.0;
}
bool operator ==(const node x) {
return l == x.l && r == x.r;
}
};
db ans;
void solve(vector<node> &a, vector<node> &b, int l, int r) {
if (a.empty() || b.empty()) return;
if (a.size() == 1 && b.size() == 1) {
if (a[0] == b[0]) {
// cout<<"AD:"<<a[0].len() * a[0].prb * b[0].prb / 3.0<<endl;
ans += a[0].len() * a[0].prb * b[0].prb / 3.0;
return;
}
if (a[0].len() == 0 && b[0].len() == 0) {
ans += abs(a[0].l - b[0].l) * a[0].prb * b[0].prb;
return;
}
if (a[0].len() == 0) {
ans += fabs(a[0].l - b[0].mid()) * a[0].prb * b[0].prb;
return;
}
if (b[0].len() == 0) {
ans += fabs(b[0].l - a[0].mid()) * a[0].prb * b[0].prb;
return;
}
}
int mid = (l + r) >> 1;
// cout<<mid<<" "<<a[0].l<<" "<<a[0].r<<" "<<b[0].l<<" "<<b[0].r<<endl;
vector<node> la, ra, lb, rb;
for (auto x : a) {
if (x.r <= mid) la.push_back(x);
else if (x.l >= mid) ra.push_back(x);
else {
auto s = node(x.l, mid, x.prb * (mid - x.l) / (x.r - x.l));
auto t = node(mid, x.r, x.prb * (x.r - mid) / (x.r - x.l));
la.push_back(s);
ra.push_back(t);
}
}
for (auto x : b) {
if (x.r <= mid) lb.push_back(x);
else if (x.l >= mid) rb.push_back(x);
else {
auto s = node(x.l, mid, x.prb * (mid - x.l) / (x.r - x.l));
auto t = node(mid, x.r, x.prb * (x.r - mid) / (x.r - x.l));
lb.push_back(s);
rb.push_back(t);
}
}
db s = 0, t = 0;
db sp = 0, tp = 0;
for (auto x : la) s += x.mid() * x.prb, sp += x.prb;
for (auto x : rb) t += x.mid() * x.prb, tp += x.prb;
// cout<<"ED:"<<s<<" "<<t<<" "<<sp<<" "<<tp<<endl;
ans += t * sp - s * tp;
s = t = sp = tp = 0;
for (auto x : lb) s += x.mid() * x.prb, sp += x.prb;
for (auto x : ra) t += x.mid() * x.prb, tp += x.prb;
// cout<<"ED:"<<s<<" "<<t<<" "<<sp<<" "<<tp<<endl;
ans += t * sp - s * tp;
solve(la, lb, l, mid);
solve(ra, rb, mid, r);
}
vector<node> a, b;
signed main() {
scanf("%lld%lld", &n, &m);
int sa = 0, sb = 0;
for (int i = 1; i <= n; i++) {
int x, y;
scanf("%lld%lld", &x, &y);
a.push_back(node(x, y));
sa += y - x;
}
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%lld%lld", &x, &y);
b.push_back(node(x, y));
sb += y - x;
}
if (sa == 0) for (auto &x : a) x.prb = 1.0 / n;
else for (auto &x : a) x.prb = x.len() * 1.0 / sa;
if (sb == 0) for (auto &x : b) x.prb = 1.0 / m;
else for (auto &x : b) x.prb = x.len() * 1.0 / sb;
solve(a, b, (int)-1e9, (int)1e9);
printf("%.12lf\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3580kb
input:
1 1 0 1 0 1
output:
0.333333333333
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3484kb
input:
1 1 0 1 1 1
output:
0.500000000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3632kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
666666666.666666626930
result:
ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3584kb
input:
1 1 -1000000000 0 0 1000000000
output:
1000000000.000000000000
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
1 1 -1000000000 -1000000000 -1000000000 1000000000
output:
1000000000.000000000000
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
1 1 -999999999 1000000000 -1000000000 -1000000000
output:
1000000000.499999880791
result:
ok found '1000000000.499999881', expected '1000000000.500000000', error '0.000000000'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3560kb
input:
1 1 -1000000000 1000000000 -999999999 -999999999
output:
999999999.000000000000
result:
ok found '999999999.000000000', expected '999999999.000000000', error '0.000000000'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3480kb
input:
1 1 1000000000 1000000000 -1000000000 -1000000000
output:
2000000000.000000000000
result:
ok found '2000000000.000000000', expected '2000000000.000000000', error '0.000000000'
Test #9:
score: 0
Accepted
time: 2ms
memory: 4156kb
input:
1000 1000 -2175 -2174 -1068 -1065 -1721 -1718 777 834 1162 1169 -3529 -3524 3966 3993 1934 1952 -234 -223 -4967 -4947 8500 8510 5272 5276 -6048 -6033 -34 -22 700 705 -7890 -7886 5538 5543 4114 4126 -9201 -9162 -1521 -1519 -5103 -5100 439 441 993 997 -1684 -1680 -8413 -8404 6724 6728 -3242 -3239 2616...
output:
6717.117145739559
result:
ok found '6717.117145740', expected '6717.117145739', error '0.000000000'
Test #10:
score: -100
Wrong Answer
time: 1ms
memory: 4080kb
input:
1000 1000 -5010 -4999 -2128 -2113 -5798 -5765 705 713 -3956 -3938 -5308 -5307 6759 6772 -772 -770 -860 -859 2308 2323 -5500 -5500 5140 5177 -6747 -6733 7509 7511 8864 8870 -6382 -6374 1901 1904 -5763 -5760 3019 3027 2962 2963 -314 -301 -222 -203 -726 -724 -62 -58 -1203 -1195 -5216 -5215 -4298 -4292 ...
output:
6682.580768008042
result:
wrong answer 1st numbers differ - expected: '6682.5811275', found: '6682.5807680', error = '0.0000001'