Submission #587459

#	Time	Username	Problem	Language	Result	Execution time	Memory
587459		AlperenT	Game (IOI13_game)	C++17	63 / 100	1524 ms	256000 KiB

game

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

struct NodeY{
    long long val = 0;

    NodeY *lptr_y = nullptr, *rptr_y = nullptr;
};

struct NodeX{
    NodeX *lptr_x = nullptr, *rptr_x = nullptr;
    NodeY *ptr_y = nullptr;
};
 
struct TwoDimSegTree{
    NodeX *root;

    long long query_y(NodeY *v, int tl, int tr, int ly, int ry){
        if(!v || ly > ry) return 0;
        else if(tl == ly && tr == ry) return v->val;
        else{
            int tm = tl + (tr - tl) / 2;

            return __gcd(query_y(v->lptr_y, tl, tm, ly, min(ry, tm)), query_y(v->rptr_y, tm + 1, tr, max(ly, tm + 1), ry));
        }
    }

    long long query_x(NodeX *v, int tl, int tr, int lx, int rx, int ly, int ry){
        if(!v || lx > rx) return 0;
        else if(tl == lx && tr == rx) return query_y(v->ptr_y, 0, M - 1, ly, ry);
        else{
            int tm = tl + (tr - tl) / 2;

            return __gcd(query_x(v->lptr_x, tl, tm, lx, min(tm, rx), ly, ry), query_x(v->rptr_x, tm + 1, tr, max(lx, tm + 1), rx, ly, ry));
        }
    }

    void update_y(NodeY *&v, int l, int r, int pos, long long val){
        if(!v) v = new NodeY();

        if(l == r) v->val = val;
        else{
            int m = l + (r - l) / 2;

            if(pos <= m) update_y(v->lptr_y, l, m, pos, val);
            else update_y(v->rptr_y, m + 1, r, pos, val);

            v->val = __gcd(v->lptr_y ? v->lptr_y->val : 0, v->rptr_y ? v->rptr_y->val : 0);
        }
    }

    void update_x(NodeX *&v, int l, int r, int posx, int posy, long long val){
        if(!v) v = new NodeX();

        if(l == r) update_y(v->ptr_y, 0, M - 1, posy, val);
        else{
            int m = l + (r - l) / 2;

            if(posx <= m) update_x(v->lptr_x, l, m, posx, posy, val);
            else update_x(v->rptr_x, m + 1, r, posx, posy, val);

            val = __gcd(v->lptr_x ? query_y(v->lptr_x->ptr_y, 0, M - 1, posy, posy) : 0, v->rptr_x ? query_y(v->rptr_x->ptr_y, 0, M - 1, posy, posy) : 0);

            update_y(v->ptr_y, 0, M - 1, posy, val);
        }
    }
};
 
TwoDimSegTree sgt;
 
void init(int R, int C){
    N = R, M = C;
}
 
void update(int P, int Q, long long K) {
    sgt.update_x(sgt.root, 0, N - 1, P, Q, K);
}
 
long long calculate(int P, int Q, int U, int V) {
    return sgt.query_x(sgt.root, 0, N - 1, P, U, Q, V);
}

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