QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#686944 | #6439. Cloud Retainer's Game | catch-up-from-behind | AC ✓ | 735ms | 5472kb | C++17 | 3.4kb | 2024-10-29 16:26:49 | 2024-10-29 16:26:49 |
Judging History
answer
// sis puella oier
#include <bits/stdc++.h>
using namespace std;
// #define int long long
typedef long long ll;
ll read(){
ll xx = 0, f = 1; char ch = getchar();
for (;!isdigit(ch); ch = getchar())f = (ch == '-' ? -1 : 1);
for (; isdigit(ch); ch = getchar())xx = (xx << 3) + (xx << 1) + ch - '0';
return xx * f;
}
const int N = 500100;
struct node{
int val, x, lt, ls, rs, pri;
}tr[N];
int cnt = 0;
int addp(int val, int x){tr[++cnt] = node{val, x, 0, 0, 0, rand()}; return cnt;}
void doit(int x, int va){if (x != 0)tr[x].x += va, tr[x].lt += va;}
void down(int x){if (tr[x].lt != 0)doit(tr[x].ls, tr[x].lt), doit(tr[x].rs, tr[x].lt), tr[x].lt = 0;}
void split(int u, int k, int &L, int &R){
if (u == 0){L = R = 0; return ;} down(u);
if (tr[u].x <= k)L = u, split(tr[u].rs, k, tr[u].rs, R);
else R = u, split(tr[u].ls, k, L, tr[u].ls);
}
int merge(int L, int R){
if (L == 0 || R == 0)return L + R; down(L), down(R);
if (tr[L].pri >= tr[R].pri){tr[L].rs = merge(tr[L].rs, R); return L;}
else {tr[R].ls = merge(L, tr[R].ls); return R;}
}
int ans;
void work(int x){
if (x == 0)return ;
ans = max(ans, tr[x].val); down(x);
work(tr[x].ls), work(tr[x].rs);
}
int rt;
int H;
void swich(int &lst, int tmp){
int L, R;
int len = tmp - lst; len %= (H + H);
int nl = H + H - len;
// cout<<lst<<" "<<tmp<<" "<<len<<" "<<nl<<endl;
split(rt, nl, L, R);
// cout<<L<<" "<<R<<endl;
doit(L, len), doit(R, -nl);
rt = merge(R, L);
lst = tmp;
}
void out(int x){
if (x == 0)return ; down(x);
out(tr[x].ls); cout<<tr[x].x<<":"<<tr[x].val<<" "; out(tr[x].rs);
}
vector <array<int, 2>> op;
void solve(){
int n; op.clear();
rt = cnt = 0;
H = read(), n = read();
for (int i = 1, x, y; i <= n; ++i)x = read(), y = read(),
op.push_back({x, y});
n = read();
for (int i = 1, x, y; i <= n; ++i)x = read(), y = read(),
op.push_back({x, -y});
sort(op.begin(), op.end());
int lst = 0, y, L, R, p, mx, L2, R2, p2; rt = addp(0, 0);
for (int i = 0, j; i < op.size(); ){
j = i + 1; while(j < op.size() && op[j][0] == op[i][0])++j;
swich(lst, op[i][0]);
// out(rt); cout<<endl;
while(i < j){
y = abs(op[i][1]);
if (op[i][1] < 0){
split(rt, y, L, R), split(L, y - 1, L, p);
if (p != 0)++tr[p].val; rt = merge(merge(L, p), R);
split(rt, H + H - y, L, R), split(L, H + H - y - 1, L, p);
if (p != 0)++tr[p].val; rt = merge(merge(L, p), R);
}
else {
mx = -1;
split(rt, y, L, R), split(L, y - 1, L, p);
if (p != 0)mx = max(mx, tr[p].val);
split(R, H + H - y, L2, R2), split(L2, H + H - y - 1, L2, p2);
if (p2 != 0)mx = max(mx, tr[p2].val);
if (p != 0)tr[p].val = max(tr[p].val, mx);
else if (mx != -1)p = addp(mx, y);
if (p2 != 0)tr[p2].val = max(tr[p2].val, mx);
else if (mx != -1)p2 = addp(mx, H + H - y);
rt = merge(merge(L, p), merge(merge(L2, p2), R2));
}
// cout<<i<<" ::\n";
// out(rt); cout<<endl;
++i;
}
}
ans = 0; work(rt);
printf("%d\n", ans);
}
signed main(){
srand(time(0));
int _ = read();
while(_--)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3952kb
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: 238ms
memory: 5472kb
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: 735ms
memory: 5384kb
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