Submission #406663

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
406663	2021-05-18T02:04:10 Z	Marceantasy	Game (IOI13_game)	C++17	Compilation error	0 ms	0 KB

game

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

#define ll long long

static int R, C; 

struct X_NODE{
    X_NODE(int s, int e): s(s), e(e), left(NULL), right(NULL), value(0LL){}
    int s, e; 
    X_NODE *left, *right; 
    ll value; 
}; 

struct Y_NODE{
    Y_NODE(): left(NULL), right(NULL), xtree(1, C){}
    Y_NODE *left, *right; 
    X_NODE xtree; 
} *root;

ll gcd2(ll x, ll y){
    if(y == 0) return x; 
    return gcd2(y, x%y); 
}

void init(int r, int c){
    R = r, C = c; 
    root = new Y_NODE(); 
}


void upd2(X_NODE *node, int q, ll val){
    int s = node->s, e = node->e, m = (s+e)/2; 
    if(s == e){
        node->value = val; 
        return; 
    }
    X_NODE **child = &(q <= m ? node->left : node->right);
    if(*child == NULL){
        *child = new X_NODE(q, q);
        (*child)->value = val; 
    }else if((*child)->s <= q && q<=(*child)->e){
        upd2(*child, q, val); 
    }else{
        do{
            if(q <= m) e = m; 
            else s = m+1; 
            m = (s+e)/2; 
        }while((q<=m) == ((*child)->e <= m)); 
        X_NODE *nnode = new X_NODE(s, e); 
        if((*child)->e <= m) nnode->left = *child;
        else nnode->right = *child; 
        *child = nnode; 
        upd2(*child, q, val); 
    }
    node->value = gcd2(
        node->left? node->left->value:0, 
        node->right? node->right->value: 0
    );
}

ll qry2(X_NODE *node, int s, int e){
    if(node == NULL || node->s > e || node->e < s) return 0; 
    if(s <= node->s && node -> e <= e){
        return node->value; 
    }
    return gcd2(qry2(node->left, s, e), qry2(node->right, s, e)); 
}

void upd1(Y_NODE *node, int s, int e, int p, int q, ll val){
    int m = (s+e)/2; 
    if(s == e){
        upd2(&node->xtree, q, val); 
        return; 
    }
    if(p<=m){
        if(node->left == NULL) node->left = new Y_NODE(); 
        upd1(node->left, s, m, p, q, val); 
    }else{
        if(node->right == NULL) node->right = new Y_NODE(); 
        upd1(node->right, m+1, e, p, q, val); 
    }
    ll v = gcd2(
        node->left?qry2(&node->left->xtree, q, q) : 0, 
        node->right?qry2(&node->right->xtree, q, q) : 0
    );
    upd2(&node->xtree, q, v); 
}

void upd(int p, int q, ll val){
    ++p, ++q; 
    upd1(root, 1, R, p, q, val); 
}

ll qry1(Y_NODE *node, int s, int e, int p, int q, int u, int v){
    if(node == NULL || s > u || e < p) return 0; 
    if(p <= s && e <= u) return qry2(&node->xtree, q, v); 
    int m = (s+e) / 2; 
    return gcd2(
        qry1(node->left, s, m, p, q, u, v), 
        qry1(node->right, m+1, e, p, q, u, v) 
    );
}

ll calculate(int p, int q, int u, int v){
    ++p, ++q, ++u, ++v; 
    return qry1(root, 1, R, p, q, u, v);
}

Compilation message

/usr/bin/ld: /tmp/ccXFfeZZ.o: in function `main':
grader.c:(.text.startup+0x13e): undefined reference to `update'
collect2: error: ld returned 1 exit status