Submission #587315

#	Time	Username	Problem	Language	Result	Execution time	Memory
587315		AlperenT	Game (IOI13_game)	C++17	37 / 100	1133 ms	256000 KiB

game

#include <bits/stdc++.h>
#include "game.h"

using namespace std;

int n, m;

struct TwoDimSegTree{
    vector<vector<long long>> tree;

    void set(int n = 0, int m = 0){
        tree.assign(n * 4, vector<long long>(m * 4, 0));
    }

    long long queryy(int vx, int vy, int tly, int try_, int ly, int ry){
        if(ly > ry) return 0;
        else if(ly == tly && ry == try_) return tree[vx][vy];
        else{
            int tmy = tly + (try_ - tly) / 2;

            return __gcd(queryy(vx, vy * 2, tly, tmy, ly, min(ry, tmy)), queryy(vx, vy * 2 + 1, tmy + 1, try_, max(ly, tmy + 1), ry));
        }
    }

    long long queryx(int vx, int tlx, int trx, int lx, int rx, int ly, int ry){
        if(lx > rx) return 0;
        else if(lx == tlx && rx == trx) return queryy(vx, 1, 0, m - 1, ly, ry);
        else{
            int tmx = tlx + (trx - tlx) / 2;

            return __gcd(queryx(vx * 2, tlx, tmx, lx, min(rx, tmx), ly, ry), queryx(vx * 2 + 1, tmx + 1, trx, max(lx, tmx + 1), rx, ly, ry));
        }
    }

    void updatey(int vx, int lx, int rx, int vy, int ly, int ry, int posy, long long val){
        if(ly == ry){
            if(lx == rx) tree[vx][vy] = val;
            else tree[vx][vy] = __gcd(tree[vx * 2][vy], tree[vx * 2 + 1][vy]);
        }
        else{
            int my = ly + (ry - ly) / 2;

            if(posy <= my) updatey(vx, lx, rx, vy * 2, ly, my, posy, val);
            else updatey(vx, lx, rx, vy * 2 + 1, my + 1, ry, posy, val);

            tree[vx][vy] = __gcd(tree[vx][vy * 2], tree[vx][vy * 2 + 1]);
        }
    }

    void updatex(int vx, int lx, int rx, int posx, int posy, long long val){
        if(lx != rx){
            int mx = lx + (rx - lx) / 2;

            if(posx <= mx) updatex(vx * 2, lx, mx, posx, posy, val);
            else updatex(vx * 2 + 1, mx + 1, rx, posx, posy, val);
        }

        updatey(vx, lx, rx, 1, 0, m - 1, posy, val);
    }
};

TwoDimSegTree sgt;

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

    sgt.set(n, m);
}

void update(int P, int Q, long long K) {
    sgt.updatex(1, 0, n - 1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return sgt.queryx(1, 0, n - 1, P, U, Q, V);
}

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