QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#465577#1880. Nikanor Loves GamesGenshinImpactsFaultWA 1ms9808kbC++141.8kb2024-07-07 02:09:572024-07-07 02:09:57

Judging History

你现在查看的是最新测评结果

  • [2024-07-07 02:09:57]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:9808kb
  • [2024-07-07 02:09:57]
  • 提交

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