QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#216436 | #6439. Cloud Retainer's Game | veg# | RE | 1109ms | 17520kb | C++14 | 2.0kb | 2023-10-15 18:17:38 | 2023-10-15 18:17:38 |
Judging History
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...