QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#617389 | #5435. Clamped Sequence | Cipherxzc# | WA | 1ms | 5916kb | C++23 | 3.1kb | 2024-10-06 15:18:31 | 2024-10-06 15:18:32 |
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[0] == 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;
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] += vec2[i - 1].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].l < l){
p++;
}
if (p < vec2.size() && vec2[p].l == l){
db res = ks[p - 1] * x - s[p - 1];
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 = ks[p - 1] * x - s[p - 1];
res += (sum - s[p - 1]) - (ksum - ks[p - 1]) * x;
ans += res * k;
}
}
cout << fixed << setprecision(20) << ans << endl;
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5916kb
input:
8 3 3 1 4 1 5 9 2 6
output:
3.11111111111111116045
result:
wrong output format Expected integer, but "3.11111111111111116045" found