oj.uz

Submission #620139

# Submission time Handle Problem Language Result Execution time Memory
620139 2022-08-03T01:27:22 Z Olympia Game (IOI13_game) C++17
100 / 100
 5586 ms 73368 KB 
#include <bits/stdc++.h>
#include <game.h>
using namespace std;
struct Node {
    Node* left;
    Node* right;
    long long x, y;
    long long val1, val2;
    Node (long long x, long long val) {
        this->x = x, this->y = rand(), this->left = nullptr, this->right = nullptr, this->val1 = this->val2 = val;
    }
};
long long gcd (long long a, long long b) {
    if (!a || !b) return max(a,b );
    return gcd(max(a, b) % min(a, b), min(a, b));
}
void print (Node*x) {
    if (x != nullptr) {
        print(x->left);
        print(x->right);
    }
}
long long g (Node*x) {
    return ((x == nullptr) ? 0 : x->val2);
}
void upd (Node*&x) {
    x->val2 = gcd(gcd(g(x->left), g(x->right)), x->val1);
}
pair<Node*, Node*> splitX (Node*cur, long long x) {
    if (cur == nullptr) return make_pair(nullptr, nullptr);
    if (cur->right == nullptr && cur->x <= x) {
        return make_pair(cur, nullptr);
    } 
    if (cur->left == nullptr && cur->x > x) {
        return make_pair(nullptr, cur);
    }
    if (cur->x <= x) {
        auto p = splitX(cur->right, x);
        cur->right = p.first;
        upd(cur);
        return make_pair(cur, p.second);
    } else {
        auto p = splitX(cur->left, x);
        cur->left = p.second;
        upd(cur);
        return make_pair(p.first, cur);
    }
}
Node* merge (Node* node1, Node* node2) {
    if (node1 == nullptr) return node2;
    if (node2 == nullptr) return node1;
    if (node2->y <= node1->y) {
        node2->left = merge(node1, node2->left);
        upd(node2);
        return node2;
    } else {
        node1->right = merge(node1->right, node2);
        upd(node1);
        return node1;
    }
}
 
int64_t query (Node* root, int l, int r) {
    auto p = splitX(root, l - 1); //[<= l - 1, >= l]
    auto q = splitX(p.second, r); //[>= l <= r, >r]
    long long ans = g(q.first);
    root = merge(p.first, merge(q.first, q.second));
    return ans;
}
 
void update (Node*& root, int x, long long val) {
    //update the thing at index x to be val
    auto p = splitX(root, x - 1); //<=x - 1, >= x
    auto q = splitX(p.second, x); //>= x and <= x
    root = merge(p.first, merge(new Node(x, val), q.second));
}
 
struct SegmentTree {
    Node* root;
    SegmentTree* l;
    SegmentTree* r;
    int left, right;
    SegmentTree () {
        this->l = this->r = nullptr;
    }
    SegmentTree (int left, int right) {
        this->left = left, this->right = right, this->l = nullptr, this->r = nullptr, this->root = nullptr;
    }
    void upd (int x, int y, int64_t val) {
        if (left > y || right < y) {
            return;
        }
        if (left == y && right == y) {
            update(root, x, val);
            return;
        }
        if (y >= left && y <= (left + right)/2) {
            if (l == nullptr) l = new SegmentTree(left, (left + right)/2);
            l->upd(x, y, val);
        } else {
            if (r == nullptr) r = new SegmentTree((left + right)/2 + 1, right);
            r->upd(x, y, val);
        }
        int64_t ans = 0;
        if (l != nullptr) ans = gcd(ans, query(l->root, x, x));
        if (r != nullptr) ans = gcd(ans, query(r->root, x, x));
        update(root, x, ans);
    }
    int64_t get (int x1, int y1, int x2, int y2) {
        if (left > y2 || right < y1) {
            return 0;
        }
        if (left >= y1 && right <= y2) {
            return query(root, x1, x2);
        }
        int64_t ans = 0;
        if (l != nullptr) {
            ans = gcd(ans, l->get(x1, y1, x2, y2));
        }
        if (r != nullptr) {
            ans = gcd(ans, r->get(x1, y1, x2, y2));
        }
        return ans;
    }
};

SegmentTree* st;

void init (int n, int m) {
    st = new SegmentTree(0, max(n, m) + 1);
}

void update (int x, int y, long long z) {
    st->upd(x, y, z);
}

long long calculate (int x1, int y1, int x2, int y2) {
    return st->get(x1, y1, x2, y2);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 300 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 656 ms 21864 KB Output is correct
5 Correct 739 ms 21784 KB Output is correct
6 Correct 1251 ms 19116 KB Output is correct
7 Correct 1553 ms 18904 KB Output is correct
8 Correct 802 ms 12652 KB Output is correct
9 Correct 1459 ms 18972 KB Output is correct
10 Correct 1215 ms 18760 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1505 ms 15504 KB Output is correct
13 Correct 2815 ms 11808 KB Output is correct
14 Correct 362 ms 13000 KB Output is correct
15 Correct 2977 ms 13056 KB Output is correct
16 Correct 1125 ms 13008 KB Output is correct
17 Correct 1760 ms 10148 KB Output is correct
18 Correct 3269 ms 14492 KB Output is correct
19 Correct 2593 ms 14380 KB Output is correct
20 Correct 2342 ms 13868 KB Output is correct
21 Correct 0 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 292 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 641 ms 21904 KB Output is correct
13 Correct 807 ms 21720 KB Output is correct
14 Correct 1266 ms 19204 KB Output is correct
15 Correct 1523 ms 18880 KB Output is correct
16 Correct 791 ms 12660 KB Output is correct
17 Correct 1438 ms 18952 KB Output is correct
18 Correct 1177 ms 18572 KB Output is correct
19 Correct 1475 ms 15344 KB Output is correct
20 Correct 2787 ms 11976 KB Output is correct
21 Correct 366 ms 13028 KB Output is correct
22 Correct 2905 ms 13096 KB Output is correct
23 Correct 1118 ms 12896 KB Output is correct
24 Correct 1653 ms 10116 KB Output is correct
25 Correct 2983 ms 14224 KB Output is correct
26 Correct 2513 ms 14504 KB Output is correct
27 Correct 2164 ms 13816 KB Output is correct
28 Correct 1008 ms 39052 KB Output is correct
29 Correct 2223 ms 41820 KB Output is correct
30 Correct 3729 ms 31856 KB Output is correct
31 Correct 3209 ms 30924 KB Output is correct
32 Correct 547 ms 29376 KB Output is correct
33 Correct 775 ms 29440 KB Output is correct
34 Correct 1544 ms 35480 KB Output is correct
35 Correct 1984 ms 25260 KB Output is correct
36 Correct 3856 ms 39560 KB Output is correct
37 Correct 3258 ms 39788 KB Output is correct
38 Correct 2990 ms 39204 KB Output is correct
39 Correct 2554 ms 33012 KB Output is correct
40 Correct 0 ms 212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 698 ms 21940 KB Output is correct
13 Correct 780 ms 21700 KB Output is correct
14 Correct 1349 ms 19168 KB Output is correct
15 Correct 1513 ms 19012 KB Output is correct
16 Correct 722 ms 12620 KB Output is correct
17 Correct 1362 ms 19020 KB Output is correct
18 Correct 1120 ms 18616 KB Output is correct
19 Correct 1471 ms 15376 KB Output is correct
20 Correct 2737 ms 11948 KB Output is correct
21 Correct 381 ms 13004 KB Output is correct
22 Correct 2958 ms 13032 KB Output is correct
23 Correct 1120 ms 12952 KB Output is correct
24 Correct 1671 ms 10140 KB Output is correct
25 Correct 3268 ms 14348 KB Output is correct
26 Correct 2586 ms 14484 KB Output is correct
27 Correct 2203 ms 13864 KB Output is correct
28 Correct 978 ms 39124 KB Output is correct
29 Correct 2139 ms 41660 KB Output is correct
30 Correct 3653 ms 31756 KB Output is correct
31 Correct 3203 ms 30884 KB Output is correct
32 Correct 501 ms 29392 KB Output is correct
33 Correct 751 ms 29444 KB Output is correct
34 Correct 1541 ms 35476 KB Output is correct
35 Correct 1976 ms 25264 KB Output is correct
36 Correct 3794 ms 39544 KB Output is correct
37 Correct 2988 ms 39724 KB Output is correct
38 Correct 2782 ms 39088 KB Output is correct
39 Correct 1343 ms 71168 KB Output is correct
40 Correct 3429 ms 73368 KB Output is correct
41 Correct 5586 ms 60412 KB Output is correct
42 Correct 4921 ms 58028 KB Output is correct
43 Correct 1862 ms 68020 KB Output is correct
44 Correct 811 ms 52888 KB Output is correct
45 Correct 2543 ms 32952 KB Output is correct
46 Correct 5134 ms 72084 KB Output is correct
47 Correct 5028 ms 72072 KB Output is correct
48 Correct 4751 ms 71712 KB Output is correct
49 Correct 1 ms 212 KB Output is correct