제출 #1149865

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149865		SalihSahin	게임 (IOI13_game)	C++20	0 / 100	0 ms	396 KiB

game

#include<bits/stdc++.h>
#define pb push_back
#include "game.h"
using namespace std;

const int inf = 1e9;
const int N = 20;
const int L = 0;

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 node{
    node *lc, *rc;
    long long gcd;

    node(){
        gcd = 0;
        lc = rc = nullptr;
    }
};

struct node1{
    node1 *lc, *rc;
    node *in;

    node1(){
        lc = rc = nullptr;
        in = nullptr;
    }
};

node1 *kok;

long long queryY(node *root, int l, int r, int ql, int qr){
    if(l > r || ql > qr || l > qr || r < ql) return 0;
    if(l >= ql && r <= qr){
        return root->gcd;
    }
    else{
        int m = (l + r)/2;

        if(root->lc == nullptr){
            root->lc = new node();
        }
        if(root->rc == nullptr){
            root->rc = new node();
        }

        return gcd2(queryY(root->lc, l, m, ql, qr), queryY(root->rc, m+1, r, ql, qr));
    }
}

long long queryX(node1 *root, int l, int r, int ql, int qr, int qly, int qry){
    if(l > r || ql > qr || l > qr || r < ql) return 0;
    if(l >= ql && r <= qr){
        if(root->in == nullptr){
            root->in = new node();
        }

        return queryY(root->in, L, N, qly, qry);
    }
    else{
        int m = (l + r)/2;
        if(root->lc == nullptr){
            root->lc = new node1();
        }
        if(root->rc == nullptr){
            root->rc = new node1();
        }
        return gcd2(queryX(root->lc, l, m, ql, qr, qly, qry), queryX(root->rc, m+1, r, ql, qr, qly, qry));
    }
}

void updateY(node *root, int l, int r, int y, long long val){
    if(l == r){
        root->gcd = val;
    }
    else{
        int m = (l + r)/2;

        if(root->lc == nullptr){
            root->lc = new node();
        }
        if(root->rc == nullptr){
            root->rc = new node();
        }

        if(y <= m) updateY(root->lc, l, m, y, val);
        else updateY(root->rc, m+1, r, y, val);

        root->gcd = gcd2(root->lc->gcd, root->rc->gcd);
    }
}

void updateX(node1 *root, int l, int r, int x, int y, long long val){
    if(l == r){
        if(root->in == nullptr){
            root->in = new node();
        }
        updateY(root->in, L, N, y, val);
    }
    else{
        int m = (l + r)/2;

        if(root->lc == nullptr){
            root->lc = new node1();
        }
        if(root->rc == nullptr){
            root->rc = new node1();
        }
        if(root->in == nullptr){
            root->in = new node();
        }
        if(root->rc->in == nullptr){
            root->rc->in = new node();
        }
        if(root->lc->in == nullptr){
            root->lc->in = new node();
        }

        if(x <= m) updateX(root->lc, l, m, x, y, val);
        else updateX(root->rc, m+1, r, x, y, val);

        long long lval = queryY(root->lc->in, L, N, y, y);
        long long rval = queryY(root->rc->in, L, N, y, y);
        long long updval = gcd2(lval, rval);
        updateY(root->in, L, N, y, updval);
    }
}


void init(int R, int C) {
    kok = new node1();
}

void update(int P, int Q, long long K){
    updateX(kok, L, N, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return queryX(kok, L, N, P, U, Q, V);
}

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