제출 #1309458

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309458		Jean7	게임 (IOI13_game)	C++20	36 / 100	1083 ms	146072 KiB

game

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

const int N = 2e3+3 ;

int n , m , a[N][N] ;

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

struct Segment_Tree_2D {
    long long tree[N<<2][N<<2] ;
    void buildy ( int pnode , int pl , int pr , int node , int l , int r ) {
        if ( l == r ) {
            if ( pl == pr ) {
                tree[pnode][node] = a[pl][l] ;
            }
            else {
                tree[pnode][node] = gcd2 ( tree[ple][node] , tree[pri][node] ) ;
            }
            return ;
        }
        buildy ( pnode , pl , pr , le , l , mid ) ;
        buildy ( pnode , pl , pr , ri , mid+1 , r ) ;
        tree[pnode][node] = gcd2 ( tree[pnode][le] , tree[pnode][ri] ) ;
    }
    void build ( int node , int l , int r ) {
        if ( l != r ) {
            build ( le , l , mid ) ;
            build ( ri , mid+1 , r ) ;
        }
        buildy ( node , l , r , 1 , 1 , m ) ;
    }
    void updatey ( int pnode , int pl , int pr , int node , int l , int r , int i , long long v ) {
        if ( l == r ) {
            if ( pl == pr ) {
                tree[pnode][node] = v ;
            }
            else {
                tree[pnode][node] = gcd2 ( tree[ple][node] , tree[pri][node] ) ;
            }
            return ;
        }
        if ( i <= mid ) {
            updatey ( pnode , pl , pr , le , l , mid , i , v ) ;
        }
        else {
            updatey ( pnode , pl , pr , ri , mid+1 , r , i , v ) ;
        }
        tree[pnode][node] = gcd2 ( tree[pnode][le] , tree[pnode][ri] ) ;
    }
    void update ( int node , int l , int r , int i , int j , long long v ) {
        if ( l != r ) {
            if ( i <= mid ) {
                update ( le , l , mid , i , j , v ) ;
            }
            else {
                update ( ri , mid+1 , r , i , j , v ) ;
            }
        }
        updatey ( node , l , r , 1 , 1 , m , j , v ) ;
    }
    long long queryy ( int pnode , int node , int l , int r , int x , int y ) {
        if ( l > r || l > y || r < x ) {
            return 0 ;
        }
        if ( l >= x && r <= y ) {
            return tree[pnode][node] ;
        }
        return gcd2 ( queryy ( pnode , le , l , mid , x , y ) , queryy ( pnode , ri , mid+1 , r , x , y ) ) ;
    }
    long long query ( int node , int l , int r , int x , int y , int xx , int yy ) {
        if ( l > r || l > y || r < x ) {
            return 0 ;
        }
        if ( l >= x && r <= y ) {
            return queryy ( node , 1 , 1 , m , xx , yy ) ;
        }
        return gcd2 ( query ( le , l , mid , x , y , xx , yy ) , query ( ri , mid+1 , r , x , y , xx , yy ) ) ;
    }
} seg ;

void init(int R, int C) {
    n = R ;
    m = C ;
    seg.build ( 1 , 1 , n ) ;
}

void update(int P, int Q, long long K) {
    seg.update ( 1 , 1 , n , P+1 , Q+1 , K ) ;
}

long long calculate(int P, int Q, int U, int V) {
    return seg.query ( 1 , 1 , n , P+1 , U+1 , Q+1 , V+1 ) ;
}

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