oj.uz

Submission #408810

# Submission time Handle Problem Language Result Execution time Memory
408810 2021-05-19T16:41:42 Z Marceantasy Game (IOI13_game) C++17
0 / 100
 1 ms 204 KB 
#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
    );
}
*/
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; // break condition
    if(p <= s && e <= u) return query2(&node->xtree, q, v);  // tag condition
    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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -