QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#465580 | #1880. Nikanor Loves Games | GenshinImpactsFault | WA | 1ms | 11908kb | C++14 | 2.2kb | 2024-07-07 02:15:28 | 2024-07-07 02:15:30 |
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";
// cout << ">>> "; for(int i = 1; i <= top; i++) cout << p[sta[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[sta[mid]] - f[sta[mid - 1]] >= 1ll * (p[sta[mid]] - p[sta[mid - 1]]) * p[i])
l = mid;
else r = mid - 1;
}
// cout << "### " << p[i] << " " << p[sta[l]] << "\n";
ll res = -4ll * p[i] * p[sta[l]] + f[i] + f[sta[l]];
ans = max(ans, res);
}
// for(int i = 1; i <= lp; i++) {
// for(int j = 1; j <= lp; j++) {
// ll res = -4ll * p[i] * p[j] + f[i] + f[j];
// cout << ">>> " << p[i] << " " << p[j] << " : " << res << "\n";
// }
// }
cout << ans / 4 << "." << ((abs(ans) / 2) % 2) * 5 << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 11868kb
input:
2 1 4 15 3 5 10
output:
2.5
result:
ok found '2.5000000', expected '2.5000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 11908kb
input:
1 2 2 8
output:
4.0
result:
ok found '4.0000000', expected '4.0000000', error '0.0000000'
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 11784kb
input:
3 94 68 49 51 2 63 26 85 20
output:
-94.0
result:
wrong answer 1st numbers differ - expected: '-73.0000000', found: '-94.0000000', error = '0.2876712'