Submission #854086

#	Time	Username	Problem	Language	Result	Execution time	Memory
854086		abcvuitunggio	Game (IOI13_game)	C++17	100 / 100	2198 ms	82176 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
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 Ty{
    int l,r;
    Ty* left;
    Ty* right;
    long long val;
    Ty(){};
    Ty(int l, int r){
        this->l=l;
        this->r=r;
        this->left=NULL;
        this->right=NULL;
        this->val=0LL;
    }
};
struct Tx{
    Tx* left;
    Tx* right;
    Ty t;
    Tx(){
        this->left=NULL;
        this->right=NULL;
        this->t=Ty(0,999999999);
    }
}*root;
void update2(Ty* node, int j, long long val){
    if (node->l>j||node->r<j)
        return;
    if (node->l==node->r){
        node->val=val;
        return;
    }
    int mid=(node->l+node->r)>>1;
    Ty*& nxt=(mid>=j?node->left:node->right);
    if (nxt==NULL){
        nxt=new Ty(j,j);
        nxt->val=val;
    }
    else if (j>=nxt->l&&j<=nxt->r)
        update2(nxt,j,val);
    else{
        int l=node->l,r=node->r;
        while (true){
            if ((mid>=j)!=(mid>=nxt->l))
                break;
            if (mid>=j)
                r=mid;
            else
                l=mid+1;
            mid=(l+r)>>1;
        }
        auto tmp=new Ty(l,r);
        if (mid>=nxt->l)
            tmp->left=nxt;
        else
            tmp->right=nxt;
        nxt=tmp;
        update2(nxt,j,val);
    }
    node->val=gcd2((node->left==NULL?0:node->left->val),(node->right==NULL?0:node->right->val));
}
long long get2(Ty* node, int u, int v){
    if (node==NULL||node->l>v||node->r<u)
        return 0;
    if (node->l>=u&&node->r<=v)
        return node->val;
    return gcd2(get2(node->left,u,v),get2(node->right,u,v));
}
void update(Tx* node, int l, int r, int i, int j, long long val){
    if (l==r){
        update2(&node->t,j,val);
        return;
    }
    int mid=(l+r)>>1;
    if (mid>=i){
        if (node->left==NULL)
            node->left=new Tx();
        update(node->left,l,mid,i,j,val);
    }
    else{
        if (node->right==NULL)
            node->right=new Tx();
        update(node->right,mid+1,r,i,j,val);
    }
    update2(&node->t,j,gcd2(node->left?get2(&node->left->t,j,j):0,node->right?get2(&node->right->t,j,j):0));
}
long long get(Tx* node, int l, int r, int i, int j, int u, int v){
    if (node==NULL||l>j||r<i)
        return 0;
    if (l>=i&&r<=j)
        return get2(&node->t,u,v);
    return gcd2(get(node->left,l,(l+r)>>1,i,j,u,v),get(node->right,((l+r)>>1)+1,r,i,j,u,v));
}
void init(int R, int C){
    root=new Tx();
}
void update(int P, int Q, long long K){
    update(root,0,999999999,P,Q,K);
}
long long calculate(int P, int Q, int U, int V){
    return get(root,0,999999999,P,U,Q,V);
}

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