QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#609818#8775. MountainCraftm107239WA 1ms4016kbC++142.1kb2024-10-04 14:08:192024-10-04 14:08:20

Judging History

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

  • [2024-10-04 14:08:20]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4016kb
  • [2024-10-04 14:08:19]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

struct SegTree {
    struct Node {
        int L, R, sum, val;
        Node *lc, *rc;

        Node(int _l, int _r) : L(_l), R(_r), lc(nullptr), rc(nullptr), sum(0), val(0) {}

        ~Node() {
            delete lc;
            delete rc;
        }

        Node *child(Node *&c, int _l, int _r) {
            if (!c) {
                c = new Node(_l, _r);
            }
            return c;
        }

        void pushup() {
            if (val) {
                sum = R - L + 1;
            } else {
                sum = (lc ? lc->sum : 0) + (rc ? rc->sum : 0);
            }
        }

        void add(int l, int r, int v) {
            if (l == L && r == R) {
                val += v;
                pushup();
                return;
            }
            int m = (L + R) >> 1;
            if (r <= m) {
                child(lc, L, m)->add(l, r, v);
            } else if (l > m) {
                child(rc, m + 1, R)->add(l, r, v);
            } else {
                child(lc, L, m)->add(l, m, v);
                child(rc, m + 1, R)->add(m + 1, r, v);
            }
            pushup();
        }
    };

    Node root;
    
    SegTree(int l, int r) : root(l, r) {}

    void add(int l, int r, int v) {
        root.add(std::max(root.L, l), std::min(root.R, r), v);
    }

    int query(int l, int r) {
        return root.sum;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(10);

    int q, w;
    std::cin >> q >> w;
    std::set<std::pair<int, int>> vis;
    SegTree tr(0, w);
    while (q--) {
        int x, y;
        std::cin >> x >> y;
        int l = x - y, r = x + y;

        if (vis.count({l, r})) {
            tr.add(l, r, -1);
            vis.erase({l, r});
        } else {
            tr.add(l, r, 1);
            vis.insert({l, r});
        }

        std::cout << std::sqrt(2) * std::max(0, tr.query(1, w) - 1) << '\n';
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3872kb

input:

3 10
3 2
7 3
9 6

output:

5.6568542495
12.7279220614
12.7279220614

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 3944kb

input:

5 100
31 41
59 26
31 41
59 26
31 41

output:

101.8233764909
120.2081528017
73.5391052434
0.0000000000
101.8233764909

result:

ok 5 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 4016kb

input:

100 10
6 4
2 3
7 6
5 5
3 6
7 5
5 8
10 4
9 8
0 9
9 10
9 3
2 3
10 10
8 4
10 9
0 1
1 7
0 2
3 4
10 3
3 10
7 4
7 5
1 4
0 7
1 9
5 6
8 8
7 4
8 1
3 9
2 1
5 5
2 1
10 9
8 4
0 9
10 7
4 1
9 10
8 6
5 4
1 4
0 9
9 3
4 8
5 10
7 2
8 10
7 10
3 4
2 2
8 5
0 9
5 3
1 4
6 4
0 3
8 1
1 6
3 8
8 4
6 5
10 2
2 2
8 4
6 1
2 4
6 4...

output:

11.3137084990
14.1421356237
14.1421356237
14.1421356237
14.1421356237
14.1421356237
14.1421356237
14.1421356237
14.1421356237
14.1421356237
14.1421356237
14.1421356237
14.1421356237
14.1421356237
14.1421356237
14.1421356237
14.1421356237
14.1421356237
14.1421356237
14.1421356237
14.1421356237
14.142...

result:

ok 100 numbers

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 3836kb

input:

1000 100
95 8
54 8
64 96
47 34
77 47
99 91
45 70
8 6
64 84
48 42
53 14
73 66
38 27
6 52
19 75
33 39
6 24
37 80
27 45
96 48
55 95
67 1
23 78
40 4
76 7
77 22
4 47
41 31
60 54
96 37
79 52
63 40
7 92
17 7
74 12
93 16
87 5
67 43
60 29
71 58
52 41
53 84
38 2
46 87
13 54
54 14
16 93
57 7
91 98
31 23
70 3
9...

output:

18.3847763109
42.4264068712
141.4213562373
141.4213562373
141.4213562373
141.4213562373
141.4213562373
141.4213562373
141.4213562373
141.4213562373
141.4213562373
141.4213562373
141.4213562373
141.4213562373
141.4213562373
141.4213562373
141.4213562373
141.4213562373
141.4213562373
141.4213562373
14...

result:

wrong answer 2nd numbers differ - expected: '41.0121933', found: '42.4264069', error = '0.0344828'