Submission #580784

#	Time	Username	Problem	Language	Result	Execution time	Memory
580784		Dakto	Game (IOI13_game)	C++17	63 / 100	1745 ms	256000 KiB

game

#include "game.h"

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct SegTree{
    struct Node{
        int lb, rb, mid;
        Node* l=0, *r=0;
        long long val=0;
        Node(int lb, int rb):lb(lb), rb(rb){mid=(lb+rb)/2;}
        Node* get(int ind){
            if(ind<=mid) return left();
            else return right();
        }
        Node* left(){
            if(l==0) l=new Node(lb, mid);
            return l;
        }
        Node* right(){
            if(r==0) r=new Node(mid+1, rb);
            return r;
        }
        void set(int ind, long long v){
            if(lb==ind && rb==ind){
                val=v;
                return;
            }
            get(ind)->set(ind, v);
            if(l==0) val = r->val;
            else if(r==0) val = l->val;
            else val=gcd2(l->val, r->val);
        }
        long long query(int lft, int rgh){
            if(lft<=lb && rgh>=rb) return val;
            if(lb>rgh || rb<lft) return 0;
            if(l==0 && r==0) return 0;
            if(l==0) return r->query(lft, rgh);
            if(r==0) return l->query(lft, rgh);
            return gcd2(l->query(lft, rgh), r->query(lft, rgh));
        }
    };
    Node *root;
    SegTree(int n){root=new Node(0, n);}
    void set(int ind, long long val){root->set(ind, val);}
    long long query(int lb, int rb){return root->query(lb, rb);}
    long long vl(int ind){return query(ind, ind);}
};

struct TDS{
    struct Node{
        int lb, rb, mid;
        Node* l=0, *r=0;
        SegTree val;
        int n;
        Node(int lb, int rb, int n):lb(lb), rb(rb), val(n), n(n) {mid=(lb+rb)/2;}
        Node* get(int ind){
            if(ind<=mid) return left();
            else return right();
        }
        Node* left(){
            if(l==0) l=new Node(lb, mid, n);
            return l;
        }
        Node* right(){
            if(r==0) r=new Node(mid+1, rb, n);
            return r;
        }
        void set(int x, int y, long long v){
            if(lb==x && rb==x){
                val.set(y, v);
                return;
            }
            get(x)->set(x, y, v);
            if(l==0) val.set(y,r->val.vl(y));
            else if(r==0) val.set(y, l->val.vl(y));
            else val.set(y, gcd2(l->val.vl(y), r->val.vl(y)));
        }
        long long query(int lft, int rgh, int ylft, int yrgh){
            if(lft<=lb && rgh>=rb) return val.query(ylft, yrgh);
            if(lb>rgh || rb<lft) return 0;
            if(l==0 && r==0) return 0;
            if(l==0) return r->query(lft, rgh, ylft, yrgh);
            if(r==0) return l->query(lft, rgh, ylft, yrgh);
            return gcd2(l->query(lft, rgh, ylft, yrgh), r->query(lft, rgh, ylft, yrgh));
        }
    };
    Node *root;
    TDS(int x, int y){root=new Node(0, x, y+1);};
    void set(int ind, int y, long long val){root->set(ind, y, val);}
    long long query(int lb, int rb, int xl, int xr){return root->query(lb, rb, xl, xr);}
};

TDS* tree;

void init(int R, int C) {
    tree=new TDS(R,C);
}

void update(int P, int Q, long long K) {
    tree->set(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return tree->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