제출 #29171

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
29171		nibnalin	게임 (IOI13_game)	C++14	80 / 100	9299 ms	256000 KiB

game

#include "bits/stdc++.h"
#include "game.h"
using namespace std;
inline long long gcd(long long a , long long b){
    while(b){
        long long temp = a - b * (a / b);
        a = b;
        b = temp;
    }
    return a;
}
int n , m , q , type , x , y , X , Y;
long long value;
struct node{
    long long val;
    node *left , *beech , *right;
    node(){
        val = 0LL;
        left = beech = right = NULL;
    }
    long long query(int l , int r , int ql , int qr){
        if(r < l || l > qr || r < ql)
            return 0LL;
        if(l >= ql && r <= qr)
            return val;
        int mid1 = l + (r - l + 1)/3 , mid2 = r - (r - l + 1)/3;
        return gcd((beech == NULL ) ? 0 : beech -> query(mid1 + 1 , mid2 , ql , qr) , gcd((left == NULL) ? 0 : left -> query(l , mid1 , ql , qr) ,(right == NULL) ? 0 : right -> query(mid2 + 1 , r , ql , qr)));
    }
    node* update(int l , int r , int idx , bool leaf , node *ll , node *bb , node*rr){
        if(l == r)
            if(leaf)
                val = value;
            else
                val = gcd((ll == NULL) ? 0 : ll -> val , gcd((bb == NULL) ? 0 : bb -> val , (rr == NULL) ? 0 : rr -> val));
        else{
            int mid1 = l + (r - l + 1) / 3 , mid2 = r - (r - l + 1) / 3;
            if(idx <= mid1){
                if(left == NULL)
                    left = new node();
                left = left -> update(l , mid1 , idx , leaf , (ll == NULL) ? NULL : ll -> left , (bb == NULL) ? NULL : bb -> left , (rr == NULL) ? NULL : rr -> left);
            }
            else if(idx <= mid2){
                if(beech == NULL)
                    beech = new node();
                beech = beech -> update(mid1 + 1 , mid2 , idx , leaf , (ll == NULL) ? NULL : ll -> beech , (bb == NULL) ? NULL : bb -> beech , (rr == NULL) ? NULL : rr -> beech);
            }
            else{
                if(right == NULL)
                    right = new node();
                right = right -> update(mid2 + 1 , r , idx , leaf , (ll == NULL) ? NULL : ll -> right , (bb == NULL) ? NULL : bb -> right , (rr == NULL) ? NULL : rr -> right);
            }
            val = gcd((beech == NULL) ? 0LL : beech -> val , gcd((left == NULL) ? 0LL : left -> val , (right == NULL) ? 0LL : right -> val));
        }
        return this;
    }
};
struct nodex{
    node *ychild;
    nodex *left , *beech , *right;
    nodex(){
        ychild = NULL;
        left = right = beech = NULL;
    }
    long long queryx(int l , int r , int x1 , int y1 , int x2 , int y2){
        if(r < l || l > x2 || r < x1 || ychild == NULL)
            return 0LL;
        if(l >= x1 && r <= x2)
            return ychild -> query(0 , m - 1 , y1 , y2);
        int mid1 = l + (r - l + 1)/3 , mid2 = r - (r - l + 1)/3;
        return gcd((beech == NULL) ? 0 : beech -> queryx(mid1 + 1 , mid2 , x1 , y1 , x2 , y2) , gcd((left == NULL) ? 0 : left -> queryx(l , mid1 , x1 , y1 , x2 , y2) ,(right == NULL) ? 0 :  right -> queryx(mid2 + 1 , r , x1 , y1 , x2 , y2)));
    }
    nodex* update(int l , int r , int idx , int idy){
        if(ychild == NULL)
            ychild = new node();
        if(l == r)
            ychild = ychild -> update(0 , m - 1 , idy , 1 , NULL , NULL , NULL);
        else{
            int mid1 = l + (r - l + 1)/3 , mid2 = r - (r - l + 1)/3;
            if(idx <= mid1){
                if(left == NULL)
                    left = new nodex();
                left = left -> update(l , mid1, idx , idy);
            }
            else if(idx <= mid2){
                if(beech == NULL)
                    beech = new nodex();
                beech = beech -> update(mid1 + 1 , mid2 , idx , idy);
            }
            else{
                if(right == NULL)
                    right = new nodex();
                right = right -> update(mid2 + 1 , r , idx , idy);
            }
            ychild = ychild -> update(0 , m - 1 , idy , 0 , (left == NULL) ? NULL : left -> ychild ,(beech == NULL) ? NULL : beech -> ychild ,(right == NULL) ? NULL :  right -> ychild);
        }
        return this;
    }
};
nodex * root = new nodex();
/*int main(){
    scanf("%d %d %d" , &n , &m , &q);
    while(~scanf("%d" , &type)){
        if(type & 1){
            scanf("%d %d %lld" , &x , &y , &value);
            root = root -> update(0 , n - 1 , x , y);
        }
        else{
            scanf("%d %d %d %d" , &x , &y , &X , &Y);
            printf("%lld\n" , root -> queryx(0 , n - 1 , x , y , X , Y));
        }
    }
}*/

void init(int R, int C) {
	n = R, m = C;
}
 
void update(int P, int Q, long long K) {
	//cout << "upd\n";
	value = K;
	root = root -> update(0 , n - 1 , P, Q);
}
 
long long calculate(int P, int Q, int U, int V) {
	//cout << "calc\n";
	return root -> queryx(0 , n - 1 , P , Q , U , V);
}

컴파일 시 표준 에러 (stderr) 메시지

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^

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