QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#148912 | #5433. Absolute Difference | inverno | WA | 2ms | 9984kb | C++14 | 4.7kb | 2023-08-23 20:14:59 | 2023-08-23 20:15:03 |
Judging History
answer
#include<bits/stdc++.h>
//#define LL long long
//#define ld long double
using namespace std;
typedef long double ld;
typedef long long LL;
#define wr(l, x) cout << l << " " << x << endl
const int N = 100002;
struct rec{
LL l, r;
};
rec a[N], b[N], c[N];
int n, m;
LL S1, S2;
ld S12, S22;
ld ans, S23[N], S24[N];
//区间不交
inline bool cmp(rec a, rec b) {
return a.l < b.l;
}
inline bool itrsct(int i, int j){
return (min(a[i].r, b[j].r) - max(a[i].l, b[j].l)) > 0;
}
inline ld calc1(LL a, LL b) {
ld tmp = (b - a);
return tmp * tmp / S1 / S2 * tmp / 3.0;
}
//[a,b] < [c,d]
inline ld calc0(LL a, LL b, LL c, LL d) {
if (a == b || c == d) return 0;
ld t1 = b - a, t2 = d - c;
return ((ld)(d * d - c * c) / S1 / S2 * t1 - (ld)(b * b - a * a) / S1 / S2 * t2) / 2.0;
}
inline void calc(int i, int j) {
// wr(i,j);
LL l1 = a[i].l, r1 = a[i].r;
LL l2 = b[j].l, r2 = b[j].r;
LL l3 = max(l1, l2), r3 = min(r1, r2);
// l1 r1
// l2 l3 r3 r2s
ans += calc0(l1,l3,l3,r3);
ans += calc0(l3,r3,r3,r1);
ans += calc0(l2,l3,l3,r3);
ans += calc0(l3,r3,r3,r2);
ans += calc0(l1,l3,r3,r2);
ans += calc0(l2,l3,r3,r1);
ans += calc1(l3,r3);
return ;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
LL l, r;
cin >> n >> m;
for (int i = 1;i <= n;++ i){
cin >> l >> r;
a[i] = (rec){l,r};
if (r < l) cout << "Failed\n";
S1 += r-l;
}
for (int i = 1;i <= m;++ i) {
cin >> l >> r;
b[i] = (rec){l,r};
if (r < l) cout << "Failed\n";
S2 += r-l;
}
sort(a + 1, a + 1 + n, cmp);
sort(b + 1, b + 1 + m, cmp);
if (S1 != 0 && S2 == 0) {
swap(S1, S2);
for (int i = 1;i <= n;++ i)
c[i] = a[i];
for (int i = 1;i <= m;++ i)
a[i] = b[i];
for (int i = 1;i <= n;++ i)
b[i] = c[i];
swap(n,m);
}
if (S1 == 0 && S2 != 0) {
for (int i = 1;i <= m;++ i) {
S23[i] = S23[i - 1] - (ld)(b[i].r * b[i].r - b[i].l * b[i].l) / S2 / n / 2;
S24[i] = S24[i - 1] + (ld)(b[i].r - b[i].l) / S2 / n;
}
for (int i = 1;i <= n;++ i) {
int k = upper_bound(b + 1, b + m + 1, a[i], cmp) - b;
-- k;
ans += (2 * S23[k] - S23[m]);
ans += (2 * S24[k] - S24[m]) * a[i].l;
if (b[k].l <= a[i].l && a[i].l <= b[k].r) {
ans += (ld)(a[i].l - b[k].l) * (a[i].l - b[k].l) / S2 / n / 2;
ans += (ld)(b[k].r - a[i].l) * (b[k].r - a[i].l) / S2 / n / 2;
ans += (ld)(b[k].r * b[k].r - b[k].l * b[k].l) / S2 / n / 2;
ans -= (ld)(b[k].r - b[k].l) / S2 / n * a[i].l;
}
//else ans += S23[k] + S24[k] * a[i].l;
}
cout << fixed << setprecision(10) << ans << endl;
return 0;
}
if (S1 == 0 && S2 == 0) {
for (int i = 1;i <= m;++ i) {
S23[i] = S23[i - 1] + b[i].l;
}
for (int i = 1;i <= n;++ i) {
int k = upper_bound(b + 1, b + m + 1, a[i], cmp) - b;
-- k;
ans += (ld)a[i].l * (k - (m - k)) / n / m;
ans += (- S23[k] - S23[k] + S23[m]) / n / m;
}
cout << fixed << setprecision(10) << ans << endl;
return 0;
}
for (int i = 1;i <= n;++ i){
l = a[i].l, r = a[i].r;
S12 += (ld)(r * r - l * l)/S1/S2;
}
for (int i = 1;i <= m;++ i) {
l = b[i].l, r = b[i].r;
S22 += (ld)(r * r - l * l)/S1/S2;
}
int i = 1, j = 1;
LL lsum = 0, rsum = 0;
ld lsum2 = 0, rsum2 = 0;
while (i <= n) {
LL ssum = 0;
ld ssum2 = 0;
while (j <= m && b[j].l < a[i].r && !itrsct(i,j)) {
lsum += b[j].r - b[j].l;
lsum2 += (ld)(b[j].r * b[j].r - b[j].l * b[j].l)/S1/S2;
++ j;
}
while (j <= m && itrsct(i, j)) {
calc(i, j);
ssum += b[j].r - b[j].l;
ssum2 += (ld)(b[j].r * b[j].r - b[j].l * b[j].l)/S1/S2;
++ j;
}
rsum = S2 - (lsum + ssum);
rsum2 = S22 - (lsum2 + ssum2);
LL ival = a[i].r - a[i].l;
ld ival2 = a[i].r * a[i].r - a[i].l * a[i].l;
ans += (lsum * ival2/S1/S2 - lsum2 * ival) / 2.0;
ans += (ival * rsum2 - ival2/S1/S2 * rsum) / 2.0;
lsum += ssum; lsum2 += ssum2;
++ i;
if (itrsct(i, j - 1)){
-- j;
lsum -= b[j].r - b[j].l;
lsum2 -= (ld)(b[j].r * b[j].r - b[j].l * b[j].l)/S1/S2;
}
}
cout << fixed << setprecision(10) << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9872kb
input:
1 1 0 1 0 1
output:
0.3333333333
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 9828kb
input:
1 1 0 1 1 1
output:
0.5000000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 7864kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
666666666.6666666666
result:
ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 7868kb
input:
1 1 -1000000000 0 0 1000000000
output:
1000000000.0000000000
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 7876kb
input:
1 1 -1000000000 -1000000000 -1000000000 1000000000
output:
1000000000.0000000000
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #6:
score: 0
Accepted
time: 2ms
memory: 7764kb
input:
1 1 -999999999 1000000000 -1000000000 -1000000000
output:
1000000000.5000000000
result:
ok found '1000000000.500000000', expected '1000000000.500000000', error '0.000000000'
Test #7:
score: 0
Accepted
time: 2ms
memory: 9984kb
input:
1 1 -1000000000 1000000000 -999999999 -999999999
output:
999999999.0000000005
result:
ok found '999999999.000000000', expected '999999999.000000000', error '0.000000000'
Test #8:
score: 0
Accepted
time: 2ms
memory: 9892kb
input:
1 1 1000000000 1000000000 -1000000000 -1000000000
output:
2000000000.0000000000
result:
ok found '2000000000.000000000', expected '2000000000.000000000', error '0.000000000'
Test #9:
score: -100
Wrong Answer
time: 2ms
memory: 7836kb
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.1170590434
result:
wrong answer 1st numbers differ - expected: '6717.1171457', found: '6717.1170590', error = '0.0000000'