Submission #687566

#	Time	Username	Problem	Language	Result	Execution time	Memory
687566		lam	Game (IOI13_game)	C++17	63 / 100	1588 ms	256000 KiB

game

#include <bits/stdc++.h>
#include "game.h"
#define ll long long
using namespace std;
#define ff first
#define ss second
int n,m;

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

struct node
{
    node *l, *r;
    ll val;
    node()
    {
        l=r=0;
        val=0;
    }
};

struct node2
{
    node2 *l, *r;
    node *it;
    node2()
    {
        l=r=0;
        it=0;
    }
};

node2 *tree;

ll get_val(node *&x)
{
    return (x)?x->val:0LL;
}

ll get(node *&u, int ly, int ry, int l, int r)
{
    if (!u) return 0LL;
    if (ly>r||ry<l) return 0LL;
    if (ly>=l&&ry<=r) return u->val;
    int mid=(ly+ry)/2;
    return gcd2(get(u->l,ly,mid,l,r),get(u->r,mid+1,ry,l,r));
}

ll get2(node2 *&u, int lx, int rx, int l, int r, int ly, int ry)
{
    if (!u) return 0LL;
    if (lx>r||rx<l) return 0LL;
    if (lx>=l&&rx<=r) return get(u->it,1,m,ly,ry);
    int mid=(lx+rx)/2;
    return gcd2(get2(u->l,lx,mid,l,r,ly,ry),get2(u->r,mid+1,rx,l,r,ly,ry));
}

void upd(node *&u, int ly, int ry, int idx, int idy, ll val)
{
    if (!u) u=new node();
    if (ly==ry)
    {
        u->val=val;
        return;
    }
    int mid=(ly+ry)/2;
    if (idy<=mid)
        upd(u->l,ly,mid,idx,idy,val);
    else
        upd(u->r,mid+1,ry,idx,idy,val);
    u->val = gcd2(get_val(u->l),get_val(u->r));
}

void upd2(node2 *&u, int lx, int rx, int idx, int idy, ll val)
{
    if (!u) u=new node2();
    if (lx==rx)
    {
        upd(u->it,1,m,idx,idy,val);
        return;
    }
    int mid=(lx+rx)/2;
    if (idx<=mid)
        upd2(u->l,lx,mid,idx,idy,val);
    else
        upd2(u->r,mid+1,rx,idx,idy,val);
    ll L=0LL, R=0LL;
    if (u->l) L=get(u->l->it,1,m,idy,idy);
    if (u->r) R=get(u->r->it,1,m,idy,idy);
    val=gcd2(L,R);
    upd(u->it,1,m,idx,idy,val);
}



void init(int R, int C) {
    n=R; m=C;
}

void update(int P, int Q, long long K) {
    P++; Q++; upd2(tree,1,n,P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    P++; Q++; U++; V++;
    return get2(tree,1,n,P,U,Q,V);
}

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