QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#850122	#8704. 排队	hhoppitree	100 ✓	316ms	10712kb	C++17	2.2kb	2025-01-09 20:37:50	2025-01-09 20:37:51

Judging History

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

[2025-01-09 20:37:51]
评测

测评结果：100
用时：316ms
内存：10712kb

查看

[2025-01-09 20:37:50]
提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5;

mt19937 rnd;

struct Node {
    int ls, rs, fa, mn, siz;
    unsigned int key;
} p[N];

int rt;

void pushup(int k) {
    p[k].mn = min({p[p[k].ls].mn, p[p[k].rs].mn, k});
    p[k].siz = p[p[k].ls].siz + p[p[k].rs].siz + 1;
}

void split(int k, int x, int &a, int &b) {
    if (!k) {
        a = b = 0;
        return;
    }
    if (p[p[k].ls].siz + 1 <= x) {
        a = k, p[p[k].rs].fa = 0, split(p[k].rs, x - (p[p[k].ls].siz + 1), p[a].rs, b);
        if (p[k].rs) p[p[k].rs].fa = k;
    } else {
        b = k, p[p[k].ls].fa = 0, split(p[k].ls, x, a, p[b].ls);
        if (p[k].ls) p[p[k].ls].fa = k;
    }
    pushup(k);
}

int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (p[x].key < p[y].key) {
        p[p[x].rs].fa = 0;
        p[x].rs = merge(p[x].rs, y);
        if (p[x].rs) p[p[x].rs].fa = x;
        pushup(x);
        return x;
    }
    p[p[y].ls].fa = 0;
    p[y].ls = merge(x, p[y].ls);
    if (p[y].ls) p[p[y].ls].fa = y;
    pushup(y);
    return y;
}

int rnk(int x) {
    int res = p[p[x].ls].siz + 1;
    while (x != rt) {
        if (p[p[x].fa].rs == x) res += p[p[p[x].fa].ls].siz + 1;
        x = p[x].fa;
    }
    return res;
}

int find(int x, int y) {
    if (!x) return 0;
    if (y > p[p[x].ls].mn || y > x) return find(p[x].ls, y);
    return p[p[x].ls].siz + 1 + find(p[x].rs, y);
}

signed main() {
    int n, m = 0; scanf("%*d%d", &n);
    p[0].mn = n + 1;
    for (int i = 1; i <= n; ++i) {
        int opt, x; scanf("%d%d", &opt, &x);
        if (opt == 1) {
            ++m, p[m].mn = m, p[m].siz = 1, p[m].key = rnd();
            if (x) x = rnk(x);
            int a, b;
            split(rt, x, a, b);
            rt = merge(merge(a, m), b);
        } else if (opt == 2) {
            int y, a, b, c; scanf("%d", &y);
            split(rt, rnk(x) - 1, a, b);
            split(b, find(b, x), b, c);
            rt = merge(a, c);
            int d, e, f;
            split(rt, y == 0 ? 0 : rnk(y), d, e);
            split(e, find(e, x), e, f);
            rt = merge(merge(d, e), merge(b, f));
        } else {
            printf("%d\n", rnk(x));
        }
    }
    return 0;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 4

Accepted

Test #1:

score: 4

Accepted

time: 0ms

memory: 3852kb

input:

output:

result:

ok 4 lines

Test #2:

score: 4

Accepted

time: 1ms

memory: 3904kb

input:

output:

result:

ok 153 lines

Test #3:

score: 4

Accepted

time: 1ms

memory: 3892kb

input:

output:

result:

ok 159 lines

Test #4:

score: 4

Accepted

time: 0ms

memory: 3768kb

input:

output:

result:

ok 145 lines

Subtask #2:

score: 19

Accepted

Test #5:

score: 19

Accepted

time: 110ms

memory: 7568kb

input:

output:

result:

ok 179182 lines

Test #6:

score: 19

Accepted

time: 104ms

memory: 9184kb

input:

output:

result:

ok 98880 lines

Test #7:

score: 19

Accepted

time: 113ms

memory: 9336kb

input:

output:

result:

ok 148504 lines

Test #8:

score: 19

Accepted

time: 84ms

memory: 8240kb

input:

output:

result:

ok 167157 lines

Test #9:

score: 19

Accepted

time: 112ms

memory: 8936kb

input:

output:

result:

ok 145645 lines

Test #10:

score: 19

Accepted

time: 96ms

memory: 8996kb

input:

output:

result:

ok 148730 lines

Test #11:

score: 19

Accepted

time: 84ms

memory: 5288kb

input:

output:

result:

ok 234925 lines

Test #12:

score: 19

Accepted

time: 131ms

memory: 9396kb

input:

output:

result:

ok 126807 lines

Test #13:

score: 19

Accepted

time: 98ms

memory: 7912kb

input:

output:

result:

ok 126007 lines

Test #14:

score: 19

Accepted

time: 101ms

memory: 9820kb

input:

output:

result:

ok 97400 lines

Test #15:

score: 19

Accepted

time: 130ms

memory: 9956kb

input:

output:

result:

ok 117628 lines

Test #16:

score: 19

Accepted

time: 106ms

memory: 7628kb

input:

output:

result:

ok 194540 lines

Test #17:

score: 19

Accepted

time: 140ms

memory: 9328kb

input:

output:

result:

ok 74993 lines

Test #18:

score: 19

Accepted

time: 107ms

memory: 10572kb

input:

output:

result:

ok 98914 lines

Test #19:

score: 19

Accepted

time: 109ms

memory: 8596kb

input:

output:

result:

ok 166650 lines

Subtask #3:

score: 21

Accepted

Test #20:

score: 21

Accepted

time: 100ms

memory: 7032kb

input:

output:

result:

ok 222965 lines

Test #21:

score: 21

Accepted

time: 92ms

memory: 7604kb

input:

output:

result:

ok 197988 lines

Test #22:

score: 21

Accepted

time: 145ms

memory: 10712kb

input:

output:

result:

ok 58684 lines

Test #23:

score: 21

Accepted

time: 132ms

memory: 9408kb

input:

output:

result:

ok 117694 lines

Test #24:

score: 21

Accepted

time: 101ms

memory: 9236kb

input:

output:

result:

ok 147378 lines

Test #25:

score: 21

Accepted

time: 130ms

memory: 7724kb

input:

output:

result:

ok 144784 lines

Test #26:

score: 21

Accepted

time: 98ms

memory: 9684kb

input:

output:

result:

ok 116141 lines

Test #27:

score: 21

Accepted

time: 124ms

memory: 8800kb

input:

output:

result:

ok 147525 lines

Test #28:

score: 21

Accepted

time: 95ms

memory: 7276kb

input:

output:

result:

ok 148070 lines

Test #29:

score: 21

Accepted

time: 105ms

memory: 8812kb

input:

output:

result:

ok 97860 lines

Test #30:

score: 21

Accepted

time: 101ms

memory: 10208kb

input:

output:

result:

ok 96730 lines

Test #31:

score: 21

Accepted

time: 146ms

memory: 8948kb

input:

output:

result:

ok 98247 lines

Test #32:

score: 21

Accepted

time: 96ms

memory: 6972kb

input:

output:

result:

ok 167688 lines

Test #33:

score: 21

Accepted

time: 122ms

memory: 9016kb

input:

output:

result:

ok 117234 lines

Test #34:

score: 21

Accepted

time: 127ms

memory: 8232kb

input:

output:

result:

ok 149568 lines

Subtask #4:

score: 23

Accepted

Test #35:

score: 23

Accepted

time: 288ms

memory: 7768kb

input:

output:

result:

ok 99743 lines

Test #36:

score: 23

Accepted

time: 294ms

memory: 7944kb

input:

output:

result:

ok 99750 lines

Test #37:

score: 23

Accepted

time: 292ms

memory: 7044kb

input:

output:

result:

ok 99683 lines

Subtask #5:

score: 33

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Test #38:

score: 33

Accepted

time: 245ms

memory: 7380kb

input:

output:

result:

ok 98966 lines

Test #39:

score: 33

Accepted

time: 316ms

memory: 4912kb

input:

output:

result:

ok 48520 lines

Test #40:

score: 33

Accepted

time: 249ms

memory: 6428kb

input:

output:

result:

ok 108743 lines

Test #41:

score: 33

Accepted

time: 246ms

memory: 6592kb

input:

output:

result:

ok 87130 lines

Test #42:

score: 33

Accepted

time: 259ms

memory: 7644kb

input:

output:

result:

ok 74076 lines

Test #43:

score: 33

Accepted

time: 265ms

memory: 7676kb

input:

output:

result:

ok 88582 lines

Test #44:

score: 33

Accepted

time: 140ms

memory: 6152kb

input:

output:

result:

ok 198778 lines

Test #45:

score: 33

Accepted

time: 179ms

memory: 5980kb

input:

output:

result:

ok 145139 lines

Test #46:

score: 33

Accepted

time: 204ms

memory: 6504kb

input:

output:

result:

ok 147109 lines

Test #47:

score: 33

Accepted

time: 221ms

memory: 7208kb

input:

output:

result:

ok 116820 lines

Test #48:

score: 33

Accepted

time: 186ms

memory: 5648kb

input:

output:

result:

ok 150091 lines

Test #49:

score: 33

Accepted

time: 257ms

memory: 7384kb

input:

output:

result:

ok 64514 lines

Test #50:

score: 33

Accepted

time: 173ms

memory: 9116kb

input:

output:

result:

ok 109540 lines

Test #51:

score: 33

Accepted

time: 150ms

memory: 6200kb

input:

output:

result:

ok 197757 lines

Test #52:

score: 33

Accepted

time: 202ms

memory: 6724kb

input:

output:

result:

ok 119220 lines