Submission #7248

#	Time	Username	Problem	Language	Result	Execution time	Memory
7248		Rhak	Game (IOI13_game)	C++98	80 / 100	9764 ms	256000 KiB

game

#include "game.h"
#include<stdio.h>
 
long long gcd2(long long x, long long y){ return y==0? x: gcd2(y, x%y); }
 
struct _node{
    _node *d[4];
    long long GCD;
    _node(long long GCD):GCD(GCD){ d[0] = d[1] = d[2] = d[3] = 0; }
};
 
struct _IndexTree{
    int S, E;
    _node *root;
    _IndexTree(int S,int E):S(S), E(E){ root = new _node(0);}
    void update(_node* n, int s, int e, int p, long long N, _IndexTree* l, _IndexTree* r)
    {
        if( p < s || e < p) return;
        else if( p == s && e == p){
            if( N != -1) n->GCD = N;
            else n->GCD = gcd2(l?l->read(s, e):0, r?r->read(s, e):0);
            return;
        }
        long long t[4] = {0}, fn = 0;
        for(int i = 0; i < 4; i++) t[i] = n->d[i]? n->d[i]->GCD:0;
        if( e >= s+4){
            for(long long i = 0; i < 4; i++){
                int ml = (( s*(4-i) + e*i) >> 2) + 1;
                int mr = ( s*(3-i) + e*(i+1)) >> 2;
                if(i == 0) ml--;
                if( ml <= p && p <= mr ){
                    if( !n->d[i] ) n->d[i] = new _node(0);
                    update(n->d[i], ml, mr, p, N, l, r);
                    t[i] = n->d[i]->GCD;
                }
            }
        }
        else{
            for(int j = s, i = 0; j <= e; i++, j++){
              if( j != p) continue;
                if( !n->d[i] ) n->d[i] = new _node(0);
                update(n->d[i], j, j, p, N, l, r);
                t[i] = n->d[i]->GCD;
            }
        }      
        for(int i = 0; i < 4; i ++) fn = gcd2(fn, t[i]);
        n->GCD = fn;
    }
    void update(int p, long long N)
    {
        update(root, S, E, p, N, 0, 0);
    }
 
    void update(int p, _IndexTree* l, _IndexTree* r)
    {
        update(root, S, E, p, -1, l, r);
    }
 
    long long read(_node *n, int s, int e, int p, int q)
    {
        if( !n ) return 0;
        if( q < s || e < p) return 0;
        else if( p <= s && e <= q){
            return n->GCD;
        }
        int m = (s+e) >> 1;
        long long t , fn = 0;
        if( e >= s+4){
            for(long long i = 0; i < 4; i++){
                int ml = (( s*(4-i) + e*i) >> 2) + 1;
                int mr = ( s*(3-i) + e*(i+1)) >> 2;
                if(i == 0) ml--;
                t = n->d[i]? read(n->d[i], ml, mr, p, q):0;
                fn = gcd2(fn, t);
            }
        }
        else{
            for(int j = s, i = 0; j <= e; i++, j++){
                t = n->d[i]? read(n->d[i], j, j, p, q):0;
                fn = gcd2(fn, t);
            }
        }      
        return fn;
    }
 
    long long read(int s,int e){
        return read(root, S, E, s, e);
    }
};
 
struct node{
    node *left, *right;
    _IndexTree *IT;
    node(int C){
        left = right = 0;
        IT = new _IndexTree(0, C-1);
    }
};
 
struct IndexTree{
    int S, E, C;
    node* root;
    IndexTree(int S, int E, int C):S(S), E(E), C(C){
        root = new node(C);
    }
     
    void update(node* n, int s, int e, int p, int q, long long N)
    {
        if( p < s || e < p) return;  
        if( p == s && e == p){
            n->IT->update(q, N);
            return;
        }
        int m = (s+e) >> 1;
        if( p <= m ){
            if( !n->left ) n->left = new node(C);
            update(n->left, s, m, p, q, N);
        }
        else{
            if( !n->right ) n->right = new node(C);
            update(n->right, m+1, e, p, q, N);
        }
        n->IT->update(q, n->left? n->left->IT : 0, n->right? n->right->IT : 0);
    }
    void update(int p, int q, long long N)
    {
        update(root, S, E, p, q, N);
    }
 
    long long read(node *n, int s, int e, int p, int q, int u, int v)
    {
        if( !n ) return 0;
        if( q < s || e < p) return 0;
        else if( p <= s && e <= q){
            return n->IT->read(u, v);
        }
        int m = (s+e) >> 1;
        long long t1 = n->left? read(n->left, s, m, p, q, u, v):0;
        long long t2 = n->right? read(n->right, m+1, e, p, q, u, v):0;
        return gcd2(t1, t2);
    }
    long long read(int P,int Q,int U, int V)
    {
        return read(root, S, E, P, Q, U, V);
    }
}*IT;
 
void init(int R, int C){
    IT = new IndexTree(0, R-1, C);
}
 
void update(int R, int C, long long K){
    IT->update(R, C, K);
}
 
long long calculate(int P, int Q, int U, int V){
    return IT->read(P, U, Q, V);
}

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