QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#617559 | #5433. Absolute Difference | Cipherxzc# | WA | 2ms | 10172kb | C++23 | 3.9kb | 2024-10-06 16:10:36 | 2024-10-06 16:10:36 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using db = long double;
struct node{
int l, r;
db x, k;
};
bool operator<(const node &a, const node &b){
return a.l < b.l;
}
const int N = 2e5 + 5;
int n, m, l1[N], r1[N], l2[N], r2[N];
db s[N << 1], ks[N << 1]; // s: sigma(k2 * x2), ks: sigma(k2)
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
vector<int> used;
db len1 = 0, len2 = 0;
for (int i = 1; i <= n; i++){
cin >> l1[i] >> r1[i];
used.push_back(l1[i]);
used.push_back(r1[i]);
len1 += r1[i] - l1[i];
}
for (int i = 1; i <= m; i++){
cin >> l2[i] >> r2[i];
used.push_back(l2[i]);
used.push_back(r2[i]);
len2 += r2[i] - l2[i];
}
sort(used.begin(), used.end());
used.erase(unique(used.begin(), used.end()), used.end());
bool flag1 = (l1[1] == r1[1]);
bool flag2 = (l2[1] == r2[1]);
vector<node> vec1, vec2;
int p = 0;
if (flag1){
for (int i = 1; i <= n; i++){
assert(l1[i] == r1[i]);
vec1.emplace_back(l1[i], r1[i], l1[i], db(1.0) / n);
}
}else{
for (int i = 1; i <= n; i++){
while (p < used.size() && used[p] < l1[i]){
p++;
}
p++;
while (p < used.size() && used[p] <= r1[i]){
db gg = db(used[p - 1] + used[p]) / 2;
db jj = (used[p] - used[p - 1]) / len1;
vec1.emplace_back(used[p - 1], used[p], gg, jj);
p++;
}
}
}
if (flag2){
for (int i = 1; i <= m; i++){
assert(l2[i] == r2[i]);
vec2.emplace_back(l2[i], r2[i], l2[i], db(1.0) / m);
}
}else{
p = 0;
for (int i = 1; i <= m; i++){
while (p < used.size() && used[p] < l2[i]){
p++;
}
p++;
while (p < used.size() && used[p] <= r2[i]){
db gg = db(used[p - 1] + used[p]) / 2;
db jj = (used[p] - used[p - 1]) / len2;
vec2.emplace_back(used[p - 1], used[p], gg, jj);
p++;
}
}
}
sort(vec1.begin(), vec1.end());
sort(vec2.begin(), vec2.end());
// for (auto [l, r, x, k] : vec1){
// cout << l << ' ' << r << ' ' << x << ' ' << k << endl;
// }
// cout << endl;
// for (auto [l, r, x, k] : vec2){
// cout << l << ' ' << r << ' ' << x << ' ' << k << endl;
// }
s[0] = vec2[0].x * vec2[0].k;
ks[0] = vec2[0].k;
for (int i = 1; i < vec2.size(); i++){
s[i] = s[i - 1] + vec2[i].x * vec2[i].k;
ks[i] = ks[i - 1] + vec2[i].k;
}
db sum = s[vec2.size()] = s[vec2.size() - 1];
db ksum = ks[vec2.size()] = ks[vec2.size() - 1];
p = 0;
db ans = 0;
for (auto [l, r, x, k] : vec1){
while (p < vec2.size() && vec2[p].r <= l){
p++;
}
// cout << p << ' ';
if (!flag1 && !flag2 && p < vec2.size() && vec2[p].l == l){
db res = (p ? ks[p - 1] * x - s[p - 1] : 0);
res += (sum - s[p]) - (ksum - ks[p]) * x;
res = res * k + k * vec2[p].k / 3 * (r - l);
ans += res;
}else{
db res = 0;
if (p){
res += ks[p - 1] * x - s[p - 1];
res += (sum - s[p - 1]) - (ksum - ks[p - 1]) * x;
// cout << x << ' ' << ks[p - 1] << ' ' << s[p - 1] << ' ';
//cout << sum - s[p - 1] << ' ' << ksum - ks[p - 1] << ' ';
}else{
res = sum - ksum * x;
}
ans += res * k;
// cout << res * k << endl;
}
}
cout << fixed << setprecision(20) << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 10172kb
input:
1 1 0 1 0 1
output:
0.33333333333333333334
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 7836kb
input:
1 1 0 1 1 1
output:
0.50000000000000000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 7892kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
666666666.66666666668606922030
result:
ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 10172kb
input:
1 1 -1000000000 0 0 1000000000
output:
1000000000.00000000000000000000
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 8036kb
input:
1 1 -1000000000 -1000000000 -1000000000 1000000000
output:
1000000000.00000000000000000000
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 9956kb
input:
1 1 -999999999 1000000000 -1000000000 -1000000000
output:
1000000000.50000000000000000000
result:
ok found '1000000000.500000000', expected '1000000000.500000000', error '0.000000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 7920kb
input:
1 1 -1000000000 1000000000 -999999999 -999999999
output:
999999999.00000000046566128731
result:
ok found '999999999.000000000', expected '999999999.000000000', error '0.000000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 7828kb
input:
1 1 1000000000 1000000000 -1000000000 -1000000000
output:
2000000000.00000000000000000000
result:
ok found '2000000000.000000000', expected '2000000000.000000000', error '0.000000000'
Test #9:
score: -100
Wrong Answer
time: 2ms
memory: 10044kb
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:
0.37773589269810423118
result:
wrong answer 1st numbers differ - expected: '6717.1171457', found: '0.3777359', error = '0.9999438'