QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#139730 | #5433. Absolute Difference | xcyle# | WA | 1ms | 5880kb | C++20 | 3.1kb | 2023-08-14 12:46:25 | 2023-08-14 12:46:28 |
Judging History
answer
/*
_/ _/ _/_/_/ _/ _/ _/ _/_/_/_/_/
_/ _/ _/ _/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/
_/_/ _/ _/ _/ _/_/_/_/
_/ _/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/
_/ _/ _/_/_/ _/ _/_/_/_/_/ _/_/_/_/_/
*/
#include <bits/stdc++.h>
#define ll long long
#define lc(x) ((x) << 1)
#define rc(x) ((x) << 1 | 1)
#define ru(i, l, r) for (int i = (l); i <= (r); i++)
#define rd(i, r, l) for (int i = (r); i >= (l); i--)
#define mid ((l + r) >> 1)
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define sz(s) (int)s.size()
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
#define ld long double
#define maxn 200005
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
int read() {
int x = 0, w = 0; char ch = getchar();
while(!isdigit(ch)) w |= ch == '-', ch = getchar();
while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
return w ? -x : x;
}
int n, m, tmp[maxn], tot, suma, sumb, la[maxn], lb[maxn], ra[maxn], rb[maxn];
ld ans;
void doit(int tp) {
int suma = 0, sumb = 0;
vector<pii> s;
ru(i, 1, n) suma += ra[i] - la[i], s.push_back(mp(la[i], tp)), s.push_back(mp(ra[i], tp));
ru(i, 1, m) sumb += rb[i] - lb[i], s.push_back(mp(lb[i], tp ^ 1)), s.push_back(mp(rb[i], tp ^ 1));
//ru(i, 1, n) printf("%d %d\n", la[i], ra[i]);
int cntb = 0;
sort(s.begin(), s.end());
int TP[2] = {0, 0};
int l = 0;
for (auto g: s) {
int r = g.fi;
if(tp == 0) {
if(TP[tp]) {
ld p = (ld)cntb / (sumb ? sumb : m);
if(!suma) p *= 1.0 / n;
else p *= (ld)(r - l) / suma;
ans += (p - (1 - p - (TP[tp ^ 1] ? (ld)(r - l) / sumb : 0))) * (l + r) / 2;
}
if(TP[tp ^ 1]) {
if(!sumb) cntb++;
else cntb += r - l;
}
}
else {
if(TP[tp ^ 1]) {
if(!sumb) cntb++;
else cntb += r - l;
}
if(TP[tp]) {
ld p = (ld)cntb / (sumb ? sumb : m);
if(!suma) p *= 1.0 / n;
else p *= (ld)(r - l) / suma;
ans += (p - (1 - p - (TP[tp ^ 1] ? (ld)(r - l) / sumb : 0))) * (l + r) / 2;
}
}
if(tp && TP[0] && TP[1] && l != r) {
ans += (ld)(r - l) / 3 * (r - l) / suma * (r - l) / sumb;
}
TP[g.se] ^= 1;
l = r;
}
}
int main() {
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
n = read(), m = read();
ru(i, 1, n) la[i] = read(), ra[i] = read();
ru(i, 1, m) lb[i] = read(), rb[i] = read();
doit(0);
swap(n, m);
ru(i, 1, max(n, m)) swap(la[i], lb[i]), swap(ra[i], rb[i]);
doit(1);
printf("%.11Lf\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5880kb
input:
1 1 0 1 0 1
output:
0.33333333333
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5816kb
input:
1 1 0 1 1 1
output:
0.50000000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 5772kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
666666666.66666666674
result:
ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 5756kb
input:
1 1 -1000000000 0 0 1000000000
output:
1000000000.00000000000
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
1 1 -1000000000 -1000000000 -1000000000 1000000000
output:
1000000000.00000000000
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 5764kb
input:
1 1 -999999999 1000000000 -1000000000 -1000000000
output:
1000000000.50000000000
result:
ok found '1000000000.500000000', expected '1000000000.500000000', error '0.000000000'
Test #7:
score: -100
Wrong Answer
time: 1ms
memory: 5752kb
input:
1 1 -1000000000 1000000000 -999999999 -999999999
output:
-nan
result:
wrong output format Expected double, but "-nan" found