Submission #225656

#	Time	Username	Problem	Language	Result	Execution time	Memory
225656		T0p_	Game (IOI13_game)	C++14	63 / 100	1906 ms	256004 KiB

game

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

int _R, _C;

struct node2
{
    long long v;
    node2 *L, *R;
    node2()
    {
        v = 0;
        L = R = NULL;
    }
};

struct node1
{
    node2 *now;
    node1 *L, *R;
    node1()
    {
        now = new node2();
        L = R = NULL;
    }    
};

node1 *root;

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

long long query2(node2 *seg, int l, int r, int a, int b)
{
    if(!seg || r < a || b < l) return 0;
    if(a <= l && r <= b) return seg->v;
    int mid = (l+r)>>1;
    return gcd2(query2(seg->L, l, mid, a, b), query2(seg->R, mid+1, r, a, b));
}

long long query1(node1 *seg, int l, int r, int a, int b, int c, int d)
{
    if(!seg || r < a || b < l) return 0;
    if(a <= l && r <= b) return query2(seg->now, 1, _C, c, d);
    int mid = (l+r)>>1;
    return gcd2(query1(seg->L, l, mid, a, b, c, d), query1(seg->R, mid+1, r, a, b, c, d));
}

void update2(node2 *seg, int l, int r, int p, long long k)
{
    if(l == r) return void(seg->v = k);
    int mid = (l+r)>>1;
    if(p <= mid)
    {
        if(!seg->L) seg->L = new node2();
        update2(seg->L, l, mid, p, k);
    }
    else
    {
        if(!seg->R) seg->R = new node2();
        update2(seg->R, mid+1, r, p, k);
    }
    seg->v = gcd2((seg->L) ? seg->L->v : 0,(seg->R) ? seg->R->v : 0);
}

void update1(node1 *seg, int l, int r, int p, int q, long long k)
{
    if(l == r) return void(update2(seg->now, 1, _C, q, k));
    int mid = (l + r)>>1;
    if(p <= mid)
    {
        if(!seg->L) seg->L = new node1();
        update1(seg->L, l, mid, p, q, k);
    }
    else
    {
        if(!seg->R) seg->R = new node1();
        update1(seg->R, mid+1, r, p, q, k);
    }
    long long v = gcd2((seg->L) ? query2(seg->L->now, 1, _C, q, q) : 0, (seg->R) ? query2(seg->R->now, 1, _C, q, q) : 0);
    update2(seg->now, 1, _C, q, v);
}

void init(int R, int C)
{
    _R = R, _C = C;
    root = new node1();
}

void update(int P, int Q, long long K)
{
    P++, Q++;
    update1(root, 1, _R, P, Q, K);
}

long long calculate(int P, int Q, int U, int V)
{
    P++, Q++, U++, V++;
    return query1(root, 1, _R, P, U, Q, V);
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

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