제출 #619974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
619974		Olympia	Game (IOI13_game)	C++17	37 / 100	13095 ms	9420 KiB

game

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

map<int,Node*> myMap;
Node*root;

long long calculate (int x1, int y1, int x2, int y2) {
    long long ans = 0;
    for (int x = x1; x <= x2; x++) {
        if (myMap.count(x)) {
            ans = gcd(ans, query(myMap[x], y1, y2));
        }
    }
    return ans;
}

void update (int x, int y, long long z) {
    Node*cur = myMap[x];
    update(cur, y, z);
    myMap[x] = cur;
    assert(calculate(x, y, x, y) == z);
}

void init (int n, int m) {

}

    /*
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, q;
    cin >> n >> m >> q;
    vector<int64_t> ans;
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            //update
            long long x, y, z;
            cin >> x >> y >> z;
            update(x, y, z);
        } else {
            //query
            int x1, x2, y1, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            ans.push_back(calculate(x1, y1, x2, y2));
            //int ans = 0;
            //for (int x = x1; x <= x2; x++) {
            //    if (!myMap.count(x)) continue;
            //    ans = gcd(ans, query(myMap[x], y1, y2));
            //}
            //cout << ans << '\n';
        }
    }
    for (int64_t x: ans) {
        cout << x << '\n';
    }
    
}
*/

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20