QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#871782#8612. The Best Wifeucup-team296#WA 0ms3584kbC++207.6kb2025-01-25 22:05:362025-01-25 22:05:47

Judging History

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

  • [2025-01-25 22:05:47]
  • 评测
  • 测评结果：WA
  • 用时：0ms
  • 内存：3584kb
查看
  • [2025-01-25 22:05:36]
  • 提交

answer

#include <bits/stdc++.h>

#define long long long int
#define DEBUG
using namespace std;

// @author: pashka

struct splay_tree {

    struct Node;

    vector<Node> nodes;

    struct Node {
        int left, right, parent;
        int val, sum;
    };

    void recalc(int x) {
        if (x == -1) return;
        nodes[x].sum = nodes[x].val;
        if (nodes[x].left >= 0) {
            nodes[nodes[x].left].parent = x;
            nodes[x].sum += nodes[nodes[x].left].sum;
        }
        if (nodes[x].right >= 0) {
            nodes[nodes[x].right].parent = x;
            nodes[x].sum += nodes[nodes[x].right].sum;
        }
    }

    void init(int n) {
        nodes.resize(n);
        for (int i = 0; i < n; i++) {
            nodes[i].left = nodes[i].right = nodes[i].parent = -1;
            recalc(i);
        }
    }

    void rotate(int x) {
        int p = nodes[x].parent;
        int g = nodes[p].parent;
        if (nodes[p].left == x) {
            nodes[p].left = nodes[x].right;
            nodes[x].right = p;
        } else {
            nodes[p].right = nodes[x].left;
            nodes[x].left = p;
        }
        recalc(p);
        recalc(x);
        if (g >= 0) {
            if (nodes[g].left == p) nodes[g].left = x; else nodes[g].right = x;
            recalc(g);
        } else {
            nodes[x].parent = -1;
        }
    }

    void splay(int x) {
        while (nodes[x].parent >= 0) {
            int p = nodes[x].parent;
            int g = nodes[p].parent;
            if (g == -1) {
                rotate(x);
                return;
            }
            if ((x == nodes[p].right && p == nodes[g].right) ||
                (x == nodes[p].left && p == nodes[g].left)) {
                rotate(p);
                rotate(x);
            } else {
                rotate(x);
                rotate(x);
            }
        }
    }

    int max(int x) {
        while (nodes[x].right >= 0) {
            x = nodes[x].right;
        }
        splay(x);
        return x;
    }

    int merge(int x, int y) {
        if (x == -1) {
            return y;
        }
        x = max(x);
        nodes[x].right = y;
        recalc(x);
        return x;
    }

    pair<int, int> split_before(int x) {
        splay(x);
        int y = nodes[x].left;
        if (y >= 0) {
            nodes[y].parent = -1;
            nodes[x].left = -1;
            recalc(x);
        }
        return {y, x};
    }

    pair<int, int> split_after(int x) {
        splay(x);
        int y = nodes[x].right;
        if (y >= 0) {
            nodes[y].parent = -1;
            nodes[x].right = -1;
            recalc(x);
        }
        return {x, y};
    }

    int sum_before(int x) {
        splay(x);
        int y = nodes[x].left;
        if (y >= 0) {
            return nodes[y].sum + nodes[x].val;
        }
        return nodes[x].val;
    }

    void validate(int x) {
        int y = nodes[x].left;
        if (y >= 0) {
            assert(nodes[y].parent == x);
            validate(y);
        }
        y = nodes[x].right;
        if (y >= 0) {
            assert(nodes[y].parent == x);
            validate(y);
        }
    }

    void print(int x) {
        int y = nodes[x].left;
        if (y >= 0) {
            assert(nodes[y].parent == x);
            print(y);
        }
        if (x % 2 == 0) {
            cout << "+" << x / 2;
        } else {
            cout << "-" << x / 2;
        }
        y = nodes[x].right;
        if (y >= 0) {
            assert(nodes[y].parent == x);
            print(y);
        }
    }

};

void validate(splay_tree &t) {
//    for (int i = 0; i < t.nodes.size(); i++) {
//        if (t.nodes[i].parent == -1) t.validate(i);
//    }
}


int main() {
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    vector<pair<int, int>> a(n);
    set<pair<int, int>> sl;
    set<pair<int, int>> sr;

    splay_tree tree;
    tree.init(2 * n);
    for (int i = 0; i < n; i++) {
        tree.nodes[2 * i].val = tree.nodes[2 * i].sum = 1;
        tree.nodes[2 * i + 1].val = tree.nodes[2 * i + 1].sum = -1;
        tree.merge(2 * i, 2 * i + 1);
    }

    for (int x = 0; x < n; x++) {
        cin >> a[x].first >> a[x].second;
        while (!sl.empty()) {
            auto p = sl.lower_bound({a[x].first + 1, -1});
            if (p == sl.begin()) break;
            --p;
            int y = p->second;
            if (a[y].second >= a[x].second) {
                //remove y;

                auto [aa, _] = tree.split_after(2 * y);
                auto [bb, cc] = tree.split_before(2 * y + 1);
                tree.merge(aa, cc);

                auto [dd, ee] = tree.split_before(2 * x + 1);
                auto ff = tree.merge(dd, bb);
                tree.merge(ff, ee);

                validate(tree);

                sl.erase({a[y].first, y});
                sr.erase({a[y].second, y});
            } else {
                break;
            }
        }

        bool ok = true;
        {
            auto p = sl.lower_bound({a[x].first, -1});
            if (p != sl.end()) {
                int y = p->second;
                if (a[y].second <= a[x].second) {
                    ok = false;
                }
            }
        }

        if (ok) {


            sl.insert({a[x].first, x});
            sr.insert({a[x].second, x});

            {
                auto p = sr.lower_bound({a[x].first, -1});
                if (p != sr.begin()) {
                    --p;
                    int v = p->second;
                    int u = sl.begin()->second;
                    auto p2 = sl.lower_bound({a[x].first, -1});
                    if (p2 != sl.begin()) {
                        --p2;
                        int w = p2->second;
                        auto p3 = sr.lower_bound({a[w].first, -1});
                        if (p3 != sr.begin()) {
                            --p3;
                            u = p3->second;
                        }
                    }
                    auto [aa, _] = tree.split_before(2 * u);
                    auto [bb, cc] = tree.split_after(2 * v + 1);
                    tree.merge(aa, cc);
                    auto [dd, ee] = tree.split_before(2 * x + 1);
                    auto ff = tree.merge(dd, bb);
                    tree.merge(ff, ee);

                    validate(tree);

                }
            }
            {
                auto p = sl.lower_bound({a[x].second + 1, -1});
                if (p != sl.end()) {
                    auto z = p->second;
                    auto [dd, ee] = tree.split_before(2 * z + 1);
                    validate(tree);
                    tree.splay(2 * x);
                    auto ff = tree.merge(dd, 2 * x);
                    validate(tree);
                    tree.merge(ff, ee);
                    validate(tree);
                }
            }
        }

        auto first = sl.begin()->second;
        cout << tree.sum_before(first * 2) << "\n";
//
//        for (auto t: sl) {
//            cout << a[t.second].first << "-" << a[t.second].second << " ";
//        }
//        cout << "\n";
//        for (auto t: sr) {
//            cout << a[t.second].first << "-" << a[t.second].second << " ";
//        }
//        cout << "\n";
//        for (int i = 0; i < 2 * x + 2; i++) {
//            if (tree.nodes[i].parent == -1) {
//                tree.print(i);
//                cout << "\n";
//            }
//        }

    }


    return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
1 3
3 5
1 2
5 6
4 4

output:

1
1
2
2
3

result:

ok 5 number(s): "1 1 2 2 3"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3584kb

input:

100
67 72
1 100
61 65
87 91
19 77
47 97
3 85
64 97
6 92
33 36
7 27
33 44
13 98
3 62
36 97
26 39
7 35
2 92
8 64
37 83
5 89
26 87
6 96
58 71
49 96
3 85
27 65
16 93
26 70
8 97
1 100
8 93
5 59
9 92
9 99
1 100
8 81
7 66
4 78
12 52
28 42
1 36
2 100
75 81
26 61
8 86
4 44
58 74
29 100
40 77
83 100
39 59
3 9...

output:

1
1
2
2
2
2
2
2
2
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
6
6
6
6
6
6
6
6
6
6
7
7

result:

wrong answer 4th numbers differ - expected: '3', found: '2'
English 繁體中文 简体中文

Server Time: 2025-01-31 02:06:36 | OpenSource Project