Submission #406665

#	Time	Username	Problem	Language	Result	Execution time	Memory
406665		Marceantasy	Game (IOI13_game)	C++17	100 / 100	3600 ms	82124 KiB

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 update2(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){
        update2(*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; 
        update2(*child, q, val); 
    }
    node->value = gcd2(
        node->left? node->left->value:0, 
        node->right? node->right->value: 0
    );
}

ll query2(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(query2(node->left, s, e), query2(node->right, s, e)); 
}

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

void update(int p, int q, ll val){
    ++p, ++q; 
    update1(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 query2(&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);
}

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