Submission #1195173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195173		byunjaewoo	Game (IOI13_game)	C++20	0 / 100	1 ms	328 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

ll gcd__(ll a, ll b) {
    return b?gcd__(b, a%b):a;
}

const int S=1<<30;
class seg2d {
public:
    seg2d() { root=new seg1d(); }
    void update(int x, int y, ll v) { update(root, 0, S-1, x, y, v); }
    ll query(int s, int e, int l, int r) { return query(root, 0, S-1, s, e, l, r); }
private:
    class seg1d {
    public:
        seg1d *l, *r;
        seg1d() { root=new Node(); }
        void update(int k, ll v) { update(root, 0, S-1, k, v); }
        int query(int l, int r) { return query(root, 0, S-1, l, r); }
    private:
        struct Node {
            Node *l, *r;
            ll val;
        };
        Node *root;
        void update(Node *curr, int s, int e, int k, ll v) {
            if(s==e) {
                curr->val=v; return;
            }
            int m=(s+e)/2;
            if(k<=m) {
                if(!curr->l) curr->l=new Node();
                update(curr->l, s, m, k, v);
                if(curr->r) curr->val=gcd__(curr->l->val, curr->r->val);
                else curr->val=curr->l->val;
            }
            else {
                if(!curr->r) curr->r=new Node();
                update(curr->r, m+1, e, k, v);
                if(curr->l) curr->val=gcd__(curr->l->val, curr->r->val);
                else curr->val=curr->r->val;
            }
        }
        ll query(Node *curr, int s, int e, int l, int r) {
            if(!curr || s>r || l>e) return 0;
            if(l<=s && e<=r) return curr->val;
            int m=(s+e)/2;
            return gcd__(query(curr->l, s, m, l, r), query(curr->r, m+1, e, l, r));
        }
    };
    seg1d *root;
    void update(seg1d *curr, int s, int e, int x, int y, ll v) {
        curr->update(y, v);
        if(s==e) return;
        int m=(s+e)/2;
        if(x<=m) {
            if(!curr->l) curr->l=new seg1d();
            update(curr->l, s, m, x, y, v);
        }
        else {
            if(!curr->r) curr->r=new seg1d();
            update(curr->r, m+1, e, x, y, v);
        }
    }
    ll query(seg1d *curr, int s, int e, int l, int r, int ll, int rr) {
        if(!curr || s>r || l>e) return 0;
        if(l<=s && e<=r) {
            return curr->query(ll, rr);
        }
        int m=(s+e)/2;
        return gcd__(query(curr->l, s, m, l, r, ll, rr), query(curr->r, m+1, e, l, r, ll, rr));
    }
}T;

void init(int R, int C) {}

void update(int P, int Q, ll K) {
    T.update(P, Q, K);
}

ll calculate(int P, int Q, int U, int V) {
    return T.query(P, U, Q, V);
}

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