QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#686944#6439. Cloud Retainer's Gamecatch-up-from-behindAC ✓735ms5472kbC++173.4kb2024-10-29 16:26:492024-10-29 16:26:49

Judging History

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

  • [2024-10-29 16:26:49]
  • 评测
  • 测评结果:AC
  • 用时:735ms
  • 内存:5472kb
  • [2024-10-29 16:26:49]
  • 提交

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;
}


Details

Tip: Click on the bar to expand more detailed information

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