Submission #686902

#	Time	Username	Problem	Language	Result	Execution time	Memory
686902		lam	Game (IOI13_game)	C++14	0 / 100	1 ms	308 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;
int n,m;
struct node
{
    int l, r, itx;
    long long val;
    node (bool is_x)
    {
        if (is_x)
        {
            l=r=itx=0;
            val=0LL;
        }
        else
        {
            l=r=0;
            itx=-1;
            val=0LL;
        }
    }
};
vector <node> t;


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;
}

void update2(int &y, int ly, int ry, int idy, long long val)
{
    if (y==0)
    {
        y=t.size();
        t.push_back(node(0));
    }
    if (ly==ry)
    {
        t[y].val = val;
        return;
    }
    int mid=ly+(ry-ly)/2;
    if (idy<=mid)
        update2(t[y].l,ly,mid,idy,val);
    else update2(t[y].r,mid+1,ry,idy,val);
    t[y].val=gcd2(t[t[y].l].val,t[t[y].r].val);
//    cout<<ly<<' '<<ry<<": "<<t[y].val<<endl;
}

void upd(int &x, int lx, int rx, int idx, int idy, int val)
{
//    cout<<x<<"->";
    if (x==0)
    {
        x=t.size();
        t.push_back(node(1));
    }
//    cout<<lx<<' '<<rx<<" !!"<<endl;
    update2(t[x].itx,1,m,idy,val);
    if (lx==rx) return;
    int mid=lx+(rx-lx)/2;
    if (idx<=mid)
        upd(t[x].l,lx,mid,idx,idy,val);
    else upd(t[x].r,mid+1,rx,idx,idy,val);

}

int get(int y, int ly, int ry, int l, int r)
{
    if (y==0) return 0;
    if (t[y].val==0) return 0;
    if (ly>r||ry<l) return 0;
    if (ly>=l&&ry<=r) return t[y].val;
    int mid=ly+(ry-ly)/2;
    return gcd2(get(t[y].l,ly,mid,l,r),get(t[y].r,mid+1,ry,l,r));
}

int get2(int x, int lx, int rx, int l, int r, int ly, int ry)
{
    if (x==0) return 0;
    if (lx>r||rx<l) return 0;
    if (lx>=l&&rx<=r) return get(t[x].itx, 1, m, ly, ry);
    int mid=lx+(rx-lx)/2;
    return gcd2(get2(t[x].l,lx,mid,l,r,ly,ry),get2(t[x].r,mid+1,rx,l,r,ly,ry));
}

void init(int R, int C) {
    /* ... */
    n=R; m=C;
    t.push_back(node(1));
    t.push_back(node(1));
}

void update(int P, int Q, long long K) {
    /* ... */
    P++; Q++;
    int val = 1;
    upd(val,1,n,P,Q,K);

}
long long calculate(int P, int Q, int U, int V) {
    /* ... */
    P++; Q++;
    U++; V++;
    int val = 1;
    val = 1;
    return get2(val,1,n,P,U,Q,V);
}

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