QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#465577 | #1880. Nikanor Loves Games | GenshinImpactsFault | WA | 1ms | 9808kb | C++14 | 1.8kb | 2024-07-07 02:09:57 | 2024-07-07 02:09:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 400010;
int n;
int a[N], b[N], w[N];
int p[N], lp = 0;
ll ans = -1e18;
ll f[N];
int sta[N], top;
void add(int pos, int u, int x, int coef) {
int cnt = 0;
if(x >= a[u]) ++cnt; else --cnt;
if(x >= b[u]) ++cnt; else --cnt;
f[pos] += 1ll * coef * cnt * w[u];
}
bool slope(int x, int y, int z) {
// (f[y] - f[x]) / (p[y] - p[x]) > (f[z] - f[y]) / (p[z] - p[y])
return 1ll * (f[y] - f[x]) * (p[z] - p[y]) > 1ll * (f[z] - f[y]) / (p[y] - p[x]);
}
int main() {
ios::sync_with_stdio(0); cin.tie(nullptr);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i] >> b[i] >> w[i];
p[++lp] = a[i], p[++lp] = b[i];
}
p[++lp] = 1;
sort(p + 1, p + lp + 1), lp = unique(p + 1, p + lp + 1) - p - 1;
for(int i = 1; i <= n; i++) {
a[i] = lower_bound(p + 1, p + lp + 1, a[i]) - p;
b[i] = lower_bound(p + 1, p + lp + 1, b[i]) - p;
if(a[i] > b[i]) swap(a[i], b[i]);
add(1, i, 1, 1);
if(a[i] != 1) {
add(a[i], i, a[i], 1), add(a[i], i, a[i] - 1, -1);
}
if(a[i] != b[i]) {
add(b[i], i, b[i], 1), add(b[i], i, b[i] - 1, -1);
}
}
for(int i = 1; i <= lp; i++) f[i] += f[i - 1];
for(int i = 1; i <= lp; i++) {
for(; top > 1 && slope(sta[top - 1], sta[top], i); --top);
sta[++top] = i;
}
// cout << ">>> p : "; for(int i = 1; i <= lp; i++) cout << p[i] << " "; cout << "\n";
// cout << ">>> f : "; for(int i = 1; i <= lp; i++) cout << f[i] << " "; cout << "\n";
for(int i = 1; i <= lp; i++) {
int l = 1, r = top, mid;
for(; l < r;) {
mid = (l + r + 1) >> 1;
if(f[p[sta[mid]]] - f[p[sta[mid - 1]]] >= 1ll * (p[sta[mid]] - p[sta[mid - 1]]) * p[i])
l = mid;
else r = mid - 1;
}
ll res = -4ll * p[i] * p[l] + f[i] + f[l];
ans = max(ans, res);
}
cout << ans / 4 << "." << ((ans / 2) % 2) * 5 << "\n";
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 9808kb
input:
2 1 4 15 3 5 10
output:
-2.-5
result:
wrong output format Expected double, but "-2.-5" found