Submission #1181234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181234		n3rm1n	Game (IOI13_game)	C++17	0 / 100	0 ms	328 KiB

game

#include<iostream>
#include "game.h"
using namespace std;
/// struct
struct Tnode
{
    long long val;
    Tnode *l, *r;
    Tnode()
    {
        val = 0;
        l = NULL;
        r = NULL;
    }

};
struct Tree
{
    Tnode *node;
    Tree *l, *r;
    Tree()
    {
        node = NULL;
        l = NULL;
        r = NULL;
    }
};
Tree *root = NULL;
int r, c;

int qL, qR, ql, qr;
long long updPos, updpos, updvalue;

long long gcd(long long x, long long y)
{
    while (x && y)
    {
        if(x > y)x %= y;
        else y %= x;
    }
    return x + y;
}
/// query
long long query(Tnode *t, int l, int r)
{
    if(qr < l && ql > r)return 0;
    if(r < l)return 0;
    if(t == NULL)return 0;
    if(ql <= l && r <= qr)return t -> val;
    int mid = (l + r)/2;
    long long fhalf = query(t -> l, l, mid);
    long long shalf = query(t -> r, mid+1, r);
    return gcd(fhalf, shalf);
}
long long Query(Tree *t, int l, int r)
{
    if(qR < l || qL > r)return 0;
    if(r < l)return 0;
    if(t == NULL)return 0;
    if(qL <= l && r <= qR)
    {
        return query(t -> node, 0, c-1);
    }
    int mid = (l + r)/2;
    long long fhalf = Query(t -> l, l, mid);
    long long shalf = Query(t -> r, mid+1, r);
    return gcd(fhalf, shalf);
}
/// update
long long merge0(Tnode *&t0, Tnode *&t1)
{
    if(t0 == NULL && t1 == NULL)return 0;
    if(t0 == NULL)return t1 -> val;
    if(t1 == NULL)return t0 -> val;
    return gcd(t0 -> val, t1 -> val);
}
void upd(Tnode *&t, int l, int r)
{
    if(t == NULL)t = new Tnode;
    if(l == r)
    {
        t -> val = updvalue;
        return;
    }
    int mid = (l + r)/2;
    if(updpos <= mid)upd(t -> l, l, mid);
    else upd(t -> r, mid+1, r);
    t -> val = merge0(t -> l, t -> r);
}
Tnode *getValue(Tree *&t)
{
    if(t == NULL)return NULL;
    else return t -> node;
}
long long getvalue(Tnode *&t)
{
    if(t == NULL)return 0;
    return t -> val;
}
void Merge(Tnode *&t, Tnode *&t0, Tnode *&t1, int l, int r)
{
    if(t == NULL)t = new Tnode;
    if(l == r)
    {
        t -> val = gcd(getvalue(t0), getvalue(t1));
        return;
    }
    int mid = (l + r)/2;
    if(updpos <= mid)
    {
        if(t1 != NULL)t1 = t1 -> l;
        if(t0 != NULL)t0 = t0 -> l;
        Merge(t -> l, t0, t1, l, mid);
    }
    else
    {
        if(t1 != NULL)t1 = t1 -> r;
        if(t0 != NULL)t0 = t0 -> r;
        Merge(t -> r, t0, t1, mid+1, r);
    }
    t -> val = gcd(getvalue(t0), getvalue(t1));
}
void Update(Tree *t, int l, int r)
{
    if(t == NULL)t = new Tree();
    if(l == r)
    {
        upd(t -> node, 0, c-1);
        return;
    }
    int mid = (l + r)/2;
    if(updPos <= mid)Update(t -> l, l, mid);
    else Update(t -> r, mid+1, r);
    Merge(t -> node, (t -> l) -> node, (t -> r) -> node, 0, c-1);
}
void init(int R, int C) {
    r = R;
    c = C;
}

void update(int P, int Q, long long K)
{
    updPos = P;
    updpos = Q;
    updvalue = K;
    Update(root, 0, r-1);
}

long long calculate(int P, int Q, int U, int V)
{
    qL = P;
    qR = U;
    ql = Q;
    qr = V;
    long long ans = Query(root, 0, r-1);
    return ans;
}

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