QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#761840 | #5433. Absolute Difference | SGColin# | WA | 0ms | 3852kb | C++14 | 4.9kb | 2024-11-19 10:40:16 | 2024-11-19 10:40:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tii;
#define eb emplace_back
#define pb push_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}
int main() {
vector<pii> tmp, A, B;
int n = rd(), m = rd();
bool intervalA = false, intervalB = false;
rep(i, 1, n) {
int l = rd(), r = rd();
tmp.eb(l, r);
intervalA |= (l != r);
}
for (auto [l, r] : tmp) {
if (intervalA && l == r) continue;
A.eb(l, r);
}
tmp.clear();
rep(i, 1, m) {
int l = rd(), r = rd();
tmp.eb(l, r);
intervalB |= (l != r);
}
for (auto [l, r] : tmp) {
if (intervalB && l == r) continue;
B.eb(l, r);
}
if (!intervalA && !intervalB) {
double ans = 0;
sort(all(A));
sort(all(B));
int ptr = 0;
double sumL = 0, sumR = 0;
for (auto [l, r] : A) sumR += l;
for (auto [l, r] : B) {
while (ptr < A.size() && A[ptr].first <= l) {
sumL += A[ptr].first;
sumR -= A[ptr].first;
++ptr;
}
ans += l * ptr - sumL + sumR - l * (A.size() - ptr);
}
ans = ans / A.size() / B.size();
printf("%.12lf\n", ans);
return 0;
}
if (!intervalB) {swap(intervalA, intervalB); swap(A, B); swap(n, m);}
if (!intervalA) {
double ans = 0;
sort(all(A));
sort(all(B));
int ptr = 0;
double sumL = 0, sumR = 0, sumL2 = 0, sumR2 = 0;
for (auto [l, r] : B) {
sumR += r - l;
sumR2 += 1.0 * r * r - 1.0 * l * l;
}
for (auto [l, r] : A) {
while (ptr < B.size() && B[ptr].second <= l) {
auto [ll, rr] = B[ptr];
double contri = 1.0 * rr * rr - 1.0 * ll * ll;
sumL += rr - ll;
sumR -= rr - ll;
sumL2 += contri;
sumR2 -= contri;
++ptr;
}
if (ptr < B.size() && l >= B[ptr].first && l <= B[ptr].second) {
auto [ll, rr] = B[ptr];
double contri = 1.0 * rr * rr - 1.0 * ll * ll;
sumR -= rr - ll;
sumR2 -= contri;
ans += l * sumL - sumL2 / 2;
ans += sumR2 / 2 - l * sumR;
ans += l * (l - ll) - (1.0 * l * l - 1.0 * ll * ll) / 2;
ans += (1.0 * rr * rr - 1.0 * l * l) / 2 - l * (rr - l);
sumR += rr - ll;
sumR += contri;
} else {
ans += l * sumL - sumL2 / 2;
ans += sumR2 / 2 - l * sumR;
}
}
ans = ans / A.size();
printf("%.12lf\n", ans);
return 0;
}
int ptrA = 0, ptrB = 0;
vector<int> S;
for (auto [l, r] : A) S.eb(l), S.eb(r);
for (auto [l, r] : B) S.eb(l), S.eb(r);
sort(all(S));
S.erase(unique(all(S)), S.end());
auto cut = [&](vector<pii> &seg) {
vector<pii> res;
int ptr = 0;
for (auto [l, r] : seg) {
while (S[ptr] <= l) ++ptr;
while (S[ptr] <= r) {
res.eb(S[ptr - 1], S[ptr]);
++ptr;
}
}
swap(seg, res);
};
cut(A); cut(B);
int ptr = 0;
double ans = 0, sumL = 0, sumR = 0, sumL2 = 0, sumR2 = 0;
for (auto [l, r] : A) sumR += r - l, sumR2 += 1.0 * r * r - 1.0 * l * l;
for (auto [l, r] : B) {
while (ptr < A.size() && A[ptr].second <= l) {
auto [ll, rr] = A[ptr];
double contri = 1.0 * rr * rr - 1.0 * ll * ll;
sumL += rr - ll;
sumR -= rr - ll;
sumL2 += contri;
sumR2 -= contri;
++ptr;
}
double c1 = r - l;
double c2 = 1.0 * r * r - 1.0 * l * l;
if (ptr < A.size() && l == A[ptr].first && r == A[ptr].second) {
auto [ll, rr] = A[ptr];
double contri = 1.0 * rr * rr - 1.0 * ll * ll;
sumR -= rr - ll;
sumR2 -= contri;
ans += c2 * sumL / 2 - c1 * sumL2 / 2;
ans += c1 * sumR2 / 2 - c2 * sumR / 2;
ans += c1 * c1 * c1 / 3;
sumR += rr - ll;
sumR += contri;
} else {
ans += c2 * sumL / 2 - c1 * sumL2 / 2;
ans += c1 * sumR2 / 2 - c2 * sumR / 2;
}
}
printf("%.12lf\n", ans);
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3852kb
input:
1 1 0 1 0 1
output:
1.333333333333
result:
wrong answer 1st numbers differ - expected: '0.3333333', found: '1.3333333', error = '1.0000000'