QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#216436#6439. Cloud Retainer's Gameveg#RE 1109ms17520kbC++142.0kb2023-10-15 18:17:382023-10-15 18:17:38

Judging History

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

  • [2023-10-15 18:17:38]
  • 评测
  • 测评结果:RE
  • 用时:1109ms
  • 内存:17520kb
  • [2023-10-15 18:17:38]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
struct AAA {
	int x, y, t;
} a[400005];
int dp[400005][2];
map<int, int> M1, M2;
int ncnt, H;
struct Node {
	int ls, rs, mx;
} t[10000005];
void add(int &p, int l, int r, int x, int y) {
	if (!p) {
		p = ++ncnt;
		t[p].ls = t[p].rs = 0;
		t[p].mx = -1e9;
	}
	t[p].mx = max(t[p].mx, y);
	if (l == r) return;
	int mid = l + (r - l) / 2;
	if (x <= mid) add(t[p].ls, l, mid, x, y);
	else add(t[p].rs, mid + 1, r, x, y);
}
int ask(int p, int l, int r, int x) {
	if (!p || l > x) return -1e9;
	if (r <= x) return t[p].mx;
	int mid = l + (r - l) / 2;
	return max(ask(t[p].ls, l, mid, x), ask(t[p].rs, mid + 1, r, x));
}
void ins(int i) {
//	printf("M1:mod<%d> %d %d\n", (a[i].x - a[i].y + H) % H, a[i].x - a[i].y, dp[i][0]);
//	printf("M2:mod<%d> %d %d\n", (a[i].x + a[i].y) % H, a[i].x + a[i].y, dp[i][1]);
	add(M1[(a[i].x - a[i].y + H) % H], -1e9, 1e9, a[i].x - a[i].y, dp[i][0]);
	add(M2[(a[i].x + a[i].y) % H], 0, 2e9, a[i].x + a[i].y, dp[i][1]);
}
int main() {
	int T;
	cin >> T;
	while (T--) {
		M1.clear();
		M2.clear();
		ncnt = 0;
		int n, m;
		scanf("%d", &H);
		H+=H;
		scanf("%d", &n);
		for (int i = 1; i <= n; ++i) {
			int x, y;
			scanf("%d%d", &x, &y);
			a[i] = (AAA){x, y, 0};
		}
		scanf("%d", &m);
		for (int i = 1; i <= m; ++i) {
			int x, y;
			scanf("%d%d", &x, &y);
			a[i + n] = (AAA){x, y, 1};
		}
		sort(a + 1, a + n + m + 1, [](const AAA &a, const AAA &b) { return a.x < b.x; });
		ins(0);
		int ans = 0;
		for (int i = 1; i <= n + m; ++i) {
			dp[i][1] = a[i].t + max(ask(M1[(a[i].x + a[i].y) % H], -1e9, 1e9, a[i].x + a[i].y),
							ask(M2[(a[i].x + a[i].y) % H], 0, 2e9, a[i].x + a[i].y));
			dp[i][0] = a[i].t + max(ask(M1[(a[i].x - a[i].y + H) % H], -1e9, 1e9, a[i].x - a[i].y),
							ask(M2[(a[i].x - a[i].y + H) % H], 0, 2e9, a[i].x - a[i].y));
			ans = max(ans, dp[i][1]);
			ans = max(ans, dp[i][0]);
			if (!a[i].t) dp[i][0] = dp[i][1] = max(dp[i][0], dp[i][1]);
			ins(i);
		}
		printf("%d\n", ans);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 8016kb

input:

2
4
3
1 1
2 2
6 2
4
3 1
3 3
5 1
7 3
3
1
4 2
3
1 1
6 2
9 1

output:

3
3

result:

ok 2 number(s): "3 3"

Test #2:

score: 0
Accepted
time: 1109ms
memory: 17520kb

input:

5503
10
19
2 4
2 8
8 3
8 4
8 7
2 7
2 6
1 5
3 2
6 4
2 1
4 5
2 5
7 1
4 7
5 7
2 2
8 6
8 1
12
5 1
4 8
5 2
6 1
3 6
1 1
1 7
7 2
5 6
6 8
1 2
3 5
10
5
9 5
10 7
6 6
5 7
1 3
9
6 8
8 8
6 4
2 9
5 4
4 2
10 9
2 3
2 1
7
1
4 3
14
4 6
6 1
2 1
7 6
2 3
4 4
5 3
6 5
1 4
3 4
3 2
6 2
8 6
8 2
6
6
5 2
5 1
3 1
2 3
7 4
5 5
3
...

output:

2
1
2
1
3
2
0
2
4
6
1
2
0
0
1
2
1
1
0
1
0
0
2
1
1
3
2
3
3
2
1
2
0
1
5
1
1
1
0
1
3
1
2
3
3
3
2
1
0
3
1
2
2
0
4
1
1
0
1
2
2
2
1
1
1
1
2
3
2
2
2
1
1
3
1
3
0
0
3
4
5
1
1
1
1
1
0
2
0
0
3
0
2
1
1
1
0
3
2
1
3
4
3
2
2
4
2
4
2
1
2
1
0
1
3
0
3
0
2
1
0
2
5
1
2
2
1
0
1
3
0
2
3
1
4
2
2
0
2
3
2
0
0
3
1
1
1
1
3
2
...

result:

ok 5503 numbers

Test #3:

score: -100
Runtime Error

input:

54
83
1995
54 14
42 63
23 55
46 52
94 71
16 18
51 54
62 47
90 38
42 50
82 20
8 28
52 64
49 19
56 5
10 74
99 30
90 42
48 2
11 78
4 38
78 77
26 26
47 12
82 60
41 17
87 2
37 16
51 15
32 63
88 82
76 33
44 10
94 28
31 5
30 80
29 19
35 70
88 78
39 69
40 5
84 52
87 59
54 36
34 76
88 42
42 37
79 70
27 77
19...

output:


result: