QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#617458 | #5433. Absolute Difference | Cipherxzc# | WA | 1ms | 7972kb | C++23 | 3.5kb | 2024-10-06 15:39:40 | 2024-10-06 15:39:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using db = double;
struct node{
int l, r;
db x, k;
};
const int N = 1e5;
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++;
}
}
}
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) * (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: 7972kb
input:
1 1 0 1 0 1
output:
0.33333333333333331483
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5912kb
input:
1 1 0 1 1 1
output:
0.50000000000000000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 7812kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
1333333333333333248.00000000000000000000
result:
wrong answer 1st numbers differ - expected: '666666666.6666666', found: '1333333333333333248.0000000', error = '1999999998.9999998'