제출 #589841

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
589841		SlavicG	게임 (IOI13_game)	C++17	0 / 100	0 ms	212 KiB

game

#include "game.h"
#include "bits/stdc++.h"
using namespace std;

using ll = long long;

int n, m;
struct node {
    node *left, *right;
    ll val;
};

void modifj(node* i, int l, int r, int pos, ll val) {
    if(!i) {
        i = new node();
        i-> val = 0;
    }
    if(l > pos || r < pos) return;
    if(l == pos && r == pos) {
        i->val = val;
        return;
    }
    int mid = (l + r) >> 1;
    modifj(i->left, l, mid, pos, val);
    modifj(i->right, mid + 1, r, pos, val);
    i->val = __gcd(i->left->val, i->right->val);
}

ll queryj(node* i, int l, int r, int tl, int tr) {
    if(!i || l > tr || r < tl) return 0;
    if(l >= tl && r <= tr) return i->val;
    int mid = (l + r) >> 1;
    return __gcd(queryj(i->left, l, mid, tl, tr), queryj(i->right, mid + 1, r, tl, tr));
}

struct purice {
    purice *left, *right;
    node* paiu;
    ll val;
};

void modifi(purice* i, int l, int r, int posi, int posj, ll val) {
    if(!i) {
        i = new purice();
        i->val = 0;
    }
    if(l > posi || r < posi) return;
    if(l == posi && r == posi) {
        modifj(i->paiu, 0, m - 1, posj, val);
        return;
    }
    int mid = (l + r) >> 1;
    modifi(i->left, l, mid, posi, posj, val);
    modifi(i->right, mid + 1, r, posi, posj, val);
    ll new_val = __gcd(queryj(i->left->paiu, 0, m - 1, posj, posj), queryj(i->right->paiu, 0, m - 1, posj, posj));
    modifj(i->paiu, 0, m - 1, posj, new_val);
}

ll queryi(purice* i, int l, int r, int tli, int tri, int tlj, int trj) {
    if(!i || l > tri || r < tli) return 0;
    if(l >= tli && r <= tri) return queryj(i->paiu, 0, m - 1, tlj, trj);
    int mid = (l + r) >> 1;
    return __gcd(queryi(i->left, l, mid, tli, tri, tlj, trj), queryi(i->right, mid + 1, r, tli, tri, tlj, trj));
}

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

void init(int R, int C) {
    n = R, m = C;
}

purice *amogus;
void update(int P, int Q, long long K) {
    modifi(amogus, 0, n - 1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return queryi(amogus, 0, n - 1, P, U, Q, V);
}

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