Submission #1135945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135945		Luvidi	Game (IOI13_game)	C++20	63 / 100	973 ms	321536 KiB

game

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

#define ll long long

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 nd{
    ll val;
    int l,r;
    nd *ch[2];
    nd(int L,int R){
        l=L;r=R;
        val=0;
        ch[0]=NULL;
        ch[1]=NULL;
    }
    void upd(int i,ll x){
        if(l==r){
            val=x;
        }else{
            int m=(l+r)/2;
            if(i<=m){
                if(!ch[0])ch[0]=new nd(l,m);
                ch[0]->upd(i,x);
            }else{
                if(!ch[1])ch[1]=new nd(m+1,r);
                ch[1]->upd(i,x);
            }
            val=0;
            if(ch[0])val=gcd2(val,ch[0]->val);
            if(ch[1])val=gcd2(val,ch[1]->val);
        }
    }
    ll qry(int l2,int r2){
        if(l2<=l&&r<=r2)return val;
        int m=(l+r)/2;
        ll x=0;
        if(ch[0]&&l2<=m)x=gcd2(x,ch[0]->qry(l2,r2));
        if(ch[1]&&r2>m)x=gcd2(x,ch[1]->qry(l2,r2));
        return x;
    }
};

int n,m;

struct nd2{
    nd *st;
    int l,r;
    nd2 *ch[2];
    nd2(int L,int R){
        l=L;
        r=R;
        st=new nd(0,m-1);
        ch[0]=NULL;
        ch[1]=NULL;
    }
    void upd(int i,int j,ll x){
        if(l==r){
            st->upd(j,x);
        }else{
            int m=(l+r)/2;
            if(i<=m){
                if(!ch[0])ch[0]=new nd2(l,m);
                ch[0]->upd(i,j,x);
            }else{
                if(!ch[1])ch[1]=new nd2(m+1,r);
                ch[1]->upd(i,j,x);
            }
            ll x=0;
            if(ch[0])x=gcd2(x,ch[0]->st->qry(j,j));
            if(ch[1])x=gcd2(x,ch[1]->st->qry(j,j));
            st->upd(j,x);
        }
    }
    ll qry(int r1,int c1,int r2,int c2){
        if(r1<=l&&r<=r2)return st->qry(c1,c2);
        int m=(l+r)/2;
        ll x=0;
        if(ch[0]&&r1<=m)x=gcd2(x,ch[0]->qry(r1,c1,r2,c2));
        if(ch[1]&&r2>m)x=gcd2(x,ch[1]->qry(r1,c1,r2,c2));
        return x;
    }
};

nd2 *rt;

void init(int R, int C) {
    n=R;
    m=C;
    rt=new nd2(0,n-1);
}

void update(int p, int q, long long x) {
    rt->upd(p,q,x);
}

long long calculate(int r1,int c1,int r2, int c2) {
    return rt->qry(r1,c1,r2,c2);
}

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