Submission #1307080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307080		timeflew	Game (IOI13_game)	C++20	0 / 100	1 ms	576 KiB

game

/*
https://oj.uz/submission/423041
wiwiho orz
*/
#include "game.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

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

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(val);//
        idx->tag=u;
        return;
    }
    if(ql==qr) {
        idx->val=val;
        return;
    }
    int mid=(ql+qr)/2;
    if(~idx->tag) {
        if(idx->tag<=mid)
            updy(idx->l, idx->tag, idx->val, ql, mid);
        else
            updy(idx->r, idx->tag, idx->val, mid+1, qr);  
        psh(idx);      
        idx->tag=-1;
    }
    if(u<=mid)
        updy(idx->l, u, val, ql, mid);
    else
        updy(idx->r, u, val, mid+1, qr);
    psh(idx);
}

ll qryy(nodey *&idx, int u, int v, int ql ,int qr) {
    if(idx==nullptr)
        return 0;
    if((ql<=idx->tag&&idx->tag<=qr)||(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;
}

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;
    }     
    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);
    //do push up!
    ll g1=0, g2=0;
    if(idx->l)
        g1=qryy(idx->l->nd, q, q, 0, c-1);//
    if(idx->r)
        g2=qryy(idx->r->nd, q, q, 0, c-1);//
    updy(idx->nd, q, gcd(g1, g2), 0, c-1);
}

ll qryx(nodex *&idx, int p, int q, int u, int v, int ql, int qr) {
    if(!idx)
        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