Submission #224937

#	Time	Username	Problem	Language	Result	Execution time	Memory
224937		T0p_	Game (IOI13_game)	C++14	37 / 100	1862 ms	256004 KiB

game

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

long long _R, _C;

struct node2
{
    long long l, r;
    long long v;
    node2 *L, *R;
    node2(long long a, long long b)
    {
        l = a;
        r = b;
        v = 0;
        L = R = NULL;
    }  
    void extend()
    {
        if(!L && l != r)
        {
            long long mid = (l+r)>>1ll;
            L = new node2(l, mid);
            R = new node2(mid+1, r);
        }
    }
};

struct node1
{
    long long l, r;
    node2 *now;
    node1 *L, *R;
    node1(long long a, long long b, long long c, long long d)
    {
        l = a;
        r = b;
        now = new node2(c, d);
        L = R = NULL;
    }
    void extend()
    {
        if(!L && l != r)
        {
            long long mid = (l+r)>>1ll;
            L = new node1(l, mid, 1, _C);
            R = new node1(mid+1, r, 1, _C);
        }
    }
};

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

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

void update2(node2 *seg, long long p, long long k) {
    seg->extend();
    if(!(seg->l <= p && p <= seg->r)) return ;
    if(seg->l == seg->r) return void(seg->v = k);
    update2(seg->L, p, k);
    update2(seg->R, p, k);
    seg->v = gcd2(seg->L->v, seg->R->v);
}

void backtrack(node2 *seg, node2 *Lseg, node2 *Rseg, long long p) {
    seg->extend();
    Lseg->extend();
    Rseg->extend();
    if(!(seg->l <= p && p <= seg->r)) return ;
    if(seg->l == seg->r) return void(seg->v = gcd2(Lseg->v, Rseg->v));
    backtrack(seg->L, Lseg->L, Rseg->L, p);
    backtrack(seg->R, Lseg->R, Rseg->R, p);
    seg->v = gcd2(Lseg->v, Rseg->v);
}

void update1(node1 *seg, long long p, long long q, long long k) {
    seg->extend();
    if(!(seg->l <= p && p <= seg->r)) return ;
    if(seg->l == seg->r) return void(update2(seg->now, q, k));
    update1(seg->L, p, q, k);
    update1(seg->R, p, q, k);
    backtrack(seg->now, seg->L->now, seg->R->now, q);
}

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

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

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

long long calculate(int P, int Q, int U, int V) {
    long long p = P+1, q = Q+1, u = U+1, v = V+1;
    return query1(root, 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: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20