제출 #1306997

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306997		timeflew	Game (IOI13_game)	C++20	0 / 100	1 ms	584 KiB

game

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

#define ll long long

struct nodey {
    nodey *l, *r;
    ll val;
    nodey(ll v) : l(nullptr), r(nullptr), val(v) {}
};

struct nodex {
    nodex *l, *r;
    nodey *nd;
    nodex() : l(nullptr), r(nullptr), nd(nullptr) {}
};

nodex *rt=nullptr;
int r, c;

void psh(nodey *idx) {
    idx->val=gcd((idx->l?idx->l->val : 0ll), (idx->r?idx->r->val : 0ll));
}

void updy(nodey *&idx, int u, ll val, int ql, int qr) {
    if(!idx)
        idx=new nodey(0);//
    if(ql==qr) {
        idx->val=val;
        return;
    }
    int mid=(ql+qr)/2;
    if(u<=mid)
        updy(idx->l, u, val, ql, mid);
    else
        updy(idx->r, u, val, mid+1, qr);
    psh(idx);
}

void updx(nodex *&idx, int p, int q, ll val, int ql, int qr) {
    if(!idx)
        idx=new nodex();
    if(ql==qr) {
        updy(idx->nd, q, val, 0, c-1);        
        return;
    }     
    updy(idx->nd, q, val, 0, c-1); 
    int mid=(ql+qr)/2;
    if(p<=mid)
        updx(idx->l, p, q, val, ql, mid);
    else
        updx(idx->r, p, q, val, mid+1, qr);
}

ll qryy(nodey *&idx, int u, int v, int ql ,int qr) {
    if(idx==nullptr)
        return 0;
    if(u<=ql&&qr<=v) {
        return idx->val;
    }
    int mid=(ql+qr)/2;
    ll res=0;
    if(u<=mid)
        res=gcd(res, qryy(idx->l, u, v, ql, mid));
    if(mid<v)
        res=gcd(res, qryy(idx->r, u, v, mid+1, qr));
    return res;
}

ll qryx(nodex *&idx, int p, int q, int u, int v, int ql, int qr) {
    if(idx==nullptr)
        return 0;
    if(p<=ql&&qr<=q) {
        return qryy(idx->nd, u, v, 0, c-1);
    }
    int mid=(ql+qr)/2;
    ll res=0;
    if(p<=mid)
        res=gcd(res, qryx(idx->l, p, q, u, v, ql, mid));
    if(mid<q)
        res=gcd(res, qryx(idx->r, p, q, u, v, mid+1, qr));
    return res;
}

void init(int R, int C) {
    r=R, c=C;
}

void update(int P, int Q, ll K) {
    updx(rt, P, Q, K, 0, r-1);
}

ll calculate(int P, int Q, int U, int V) {
    return qryx(rt, P, U, Q, V, 0, r-1);
}

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