제출 #587311

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
587311		AlperenT	게임 (IOI13_game)	C++17	36 / 100	1314 ms	133812 KiB

game

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

using namespace std;

const int N = 2000 + 5;

int n, m;

struct TwoDimSegTree{
    long long tree[N * 4][N * 4];

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

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: 0 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20