Submission #729723

#	Time	Username	Problem	Language	Result	Execution time	Memory
729723		Jean7	Game (IOI13_game)	C++14	37 / 100	765 ms	29204 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define le (node<<1)
#define ri (node<<1|1)
#define mid ((l+r)>>1)

using namespace std ;

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

const int N = 1e5+5 ;

long long n , m , a[102][102] ;

struct Segment_Tree {
    long long tree[N<<2] ;
    void build ( int node , int l , int r ) {
        if ( l == r ) {
            tree[node] = 0 ;
        }
        else {
            build ( le , l , mid ) ;
            build ( ri , mid+1 , r ) ;
            tree[node] = gcd2 ( tree[le] , tree[ri] ) ;
        }
    }
    void update ( int node , int l , int r , int i , long long v ) {
        if ( l == r ) {
            tree[node] = v ;
        }
        else {
            if ( i <= mid ) {
                update ( le , l , mid , i , v ) ;
            }
            else {
                update ( ri , mid+1 , r , i , v ) ;
            }
            tree[node] = gcd2 ( tree[le] , tree[ri] ) ;
        }
    }
    long long query ( int node , int l , int r , int x , int y ) {
        if ( l > r || l > y || r < x ) {
            return 0ll ;
        }
        if ( l >= x && r <= y ) {
            return tree[node] ;
        }
        return gcd2 ( query ( le , l , mid , x , y ) , query ( ri , mid+1 , r , x , y ) ) ;
    }
} seg[11] ;

void init(int R, int C) {
    n = R ; m = C ;
    if ( n <= 10 ) {
        for ( int i = 1 ; i <= n ; i++ ) {
            seg[i].build ( 1 , 1 , m ) ;
        }
        return ;
    }
}

void update(int P, int Q, long long K) {
    P++ ; Q++ ;
    if ( n <= 10 ) {
        seg[P].update ( 1 , 1 , m , Q , K ) ;
        return ;
    }
    a[P][Q] = K ;
}

long long calculate(int P, int Q, int U, int V) {
    long long ret = 0 ;
    P++ ; Q++ ; U++ ; V++ ;
    if ( n <= 10 ) {
        for ( int i = P ; i <= U ; i++ ) {
            ret = gcd2 ( ret , seg[i].query ( 1 , 1 , m , Q , V ) ) ;
        }
        return ret ;
    }
    for ( int i = P ; i <= U ; i++ ) {
        for ( int j = Q ; j <= V ; j++ ) {
            ret = gcd2 ( ret , a[i][j] ) ;
        }
    }
    return ret ;
}

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