QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#824602#9776. Best Friend, Worst Enemyucup-team5052#WA 308ms14364kbC++172.2kb2024-12-21 14:51:452024-12-21 14:51:46

Judging History

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

  • [2024-12-21 14:51:46]
  • 评测
  • 测评结果:WA
  • 用时:308ms
  • 内存:14364kb
  • [2024-12-21 14:51:45]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

int n, x[400005], y[400005], d1[400005], d2[400005], cnt[400005], idx[400005], inv[400005];
vector <int> psv;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int main() {
	cin >> n;
	for (int i = 1;i <= n;i++) {
		cin >> x[i] >> y[i];
	}
	int p[2][2];
	p[0][0] = p[0][1] = p[1][0] = p[1][1] = 1;
	long long cx = rnd() % 20000 + 1, cy = rnd() % 20000 + 1;
	cx -= 10000; cy -= 10000;
	for (int i = 1;i <= n;i++) idx[i] = i;
	sort(idx + 1, idx + n + 1, [&](const int &i, const int &j) {
		return x[i] * cx + y[i] * cy < x[j] * cx + y[j] * cy;
	});
	for (int i = 1;i <= n;i++) inv[idx[i]] = i;
	memset(d1, 0x3f, sizeof(d1));
	for (int i = 1;i <= n;i++) {
		vector <int> nxt;
		for (int j : psv) {
			if (max(abs(x[i] - x[j]), abs(y[i] - y[j])) < d1[j] || abs(x[i] - x[j]) + abs(y[i] - y[j]) > d2[j]) cnt[j] = 0;
			d1[j] = min(d1[j], max(abs(x[i] - x[j]), abs(y[i] - y[j])));
			d2[j] = max(d2[j], abs(x[i] - x[j]) + abs(y[i] - y[j]));
			if (d1[j] == max(abs(x[i] - x[j]), abs(y[i] - y[j])) && d2[j] == abs(x[i] - x[j]) + abs(y[i] - y[j])) cnt[j]++;
			if (2 * d1[j] >= d2[j]) nxt.push_back(j);			
		}
		swap(psv, nxt);
		for (int k1 = 0;k1 < 2;k1++) {
			for (int k2 = 0;k2 < 2;k2++) {
				if ((2 * k1 - 1) * x[i] + (2 * k2 - 1) * y[i] > (2 * k1 - 1) * x[p[k1][k2]] + (2 * k2 - 1) * y[p[k1][k2]]) {
					p[k1][k2] = i;
				}
				d2[i] = max(d2[i], (2 * (!k1) - 1) * x[i] + (2 * (!k2) - 1) * y[i] + (2 * k1 - 1) * x[p[k1][k2]] + (2 * k2 - 1) * y[p[k1][k2]]);
			}
		}
		int pos = inv[i];
		cnt[i] = 0;
		for (int jj = max(1, pos - 50);jj <= min(n, pos + 50);jj++) {
			int j = idx[jj];
			if (j >= i) continue;
			if (max(abs(x[i] - x[j]), abs(y[i] - y[j])) < d1[i] || abs(x[i] - x[j]) + abs(y[i] - y[j]) > d2[i]) cnt[i] = 0;
			d1[i] = min(d1[i], max(abs(x[i] - x[j]), abs(y[i] - y[j])));
			d2[i] = max(d2[i], abs(x[i] - x[j]) + abs(y[i] - y[j]));
			if (d1[i] == max(abs(x[i] - x[j]), abs(y[i] - y[j])) && d2[i] == abs(x[i] - x[j]) + abs(y[i] - y[j])) cnt[i]++;
		}
		// cout << d1[i] << " " << d2[i] << endl;
		if (2 * d1[i] >= d2[i]) psv.push_back(i);
		int ans = 0;
		for (int j : psv) ans += cnt[j];
		cout << ans << endl;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 13836kb

input:

2
1 5
1 10

output:

0
2

result:

ok 2 number(s): "0 2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 11840kb

input:

4
2 5
5 3
5 7
8 5

output:

0
2
4
4

result:

ok 4 number(s): "0 2 4 4"

Test #3:

score: 0
Accepted
time: 0ms
memory: 13904kb

input:

9
3 4
3 6
4 3
4 7
5 5
6 3
6 7
7 4
7 6

output:

0
2
1
0
4
5
6
7
8

result:

ok 9 numbers

Test #4:

score: 0
Accepted
time: 2ms
memory: 9824kb

input:

13
3 5
4 4
4 5
4 6
5 3
5 4
5 5
5 6
5 7
6 4
6 5
6 6
7 5

output:

0
2
4
7
2
2
5
2
2
3
3
4
4

result:

ok 13 numbers

Test #5:

score: -100
Wrong Answer
time: 308ms
memory: 14364kb

input:

384010
200000 1000000
200000 1000001
199999 1000000
200001 1000000
200000 999999
200000 1000002
200002 1000000
200000 999998
199998 1000000
199997 1000000
200003 1000000
200000 999997
200000 1000003
199996 1000000
200004 1000000
200000 1000004
200000 999996
199995 1000000
200000 1000005
200000 99999...

output:

0
2
4
7
12
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

wrong answer 320008th numbers differ - expected: '6', found: '7'