QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#216439 | #6439. Cloud Retainer's Game | veg# | AC ✓ | 1487ms | 156364kb | C++14 | 2.0kb | 2023-10-15 18:18:49 | 2023-10-15 18:18:49 |
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[13000005];
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: 7980kb
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: 1117ms
memory: 17120kb
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: 0
Accepted
time: 1487ms
memory: 156364kb
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:
47 32 32 32 38 32 39 33 39 40 36 32 36 32 46 30 35 41 40 36 108 90 98 81 166 115 106 170 148 113 198 72 57 202 337 153 186 978 87 886 151 489 111 112 90 154 174 188 266 59 10210 1041 87 981
result:
ok 54 numbers