QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#149054 | #5433. Absolute Difference | inverno | WA | 2ms | 9908kb | C++14 | 4.7kb | 2023-08-23 23:23:31 | 2023-08-23 23:23:35 |
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) {
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;
}
cout << "---== \n";
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: 0
Wrong Answer
time: 2ms
memory: 9908kb
input:
1 1 0 1 0 1
output:
---== 0.3333333333
result:
wrong output format Expected double, but "---==" found