Submission #1195198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195198		byunjaewoo	Game (IOI13_game)	C++20	63 / 100	1171 ms	279704 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); }
        void merge(int k) {merge(root, l?l->root:NULL, r?r->root:NULL, 0, S-1, k);}
        ll query(int l, int r) { return query(root, 0, S-1, l, r); }
    private:
        struct Node {
            Node *l, *r;
            ll val;
            Node() {l=NULL, r=NULL, val=0;}
        };
        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;
            }
        }
        void merge(Node *curr, Node *curr1, Node *curr2, int s, int e, int k) {
            curr->val=gcd__(curr1?curr1->val:0, curr2?curr2->val:0);
            if(s==e) return;
            int m=(s+e)/2;
            if(k<=m) {
                if(!curr->l) curr->l=new Node();
                merge(curr->l, curr1?curr1->l:NULL, curr2?curr2->l:NULL, s, m, k);
            }
            else {
                if(!curr->r) curr->r=new Node();
                merge(curr->r, curr1?curr1->r:NULL, curr2?curr2->r:NULL, m+1, e, k);
            }
        }
        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) {
        if(s==e) {
            curr->update(y, v);
            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);
        }
        curr->merge(y);
    }
    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: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20