Submission #1091138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091138		kkkkkkkk	Game (IOI13_game)	C++14	63 / 100	1002 ms	133804 KiB

game

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

using namespace std;

long long n, m;
long long tree[4*2005][4*2005];
long long tree2[4*10][4*100005];

long long nzd(long long a, long long b) {
    if (b==0) return a;
    return nzd(b, a%b);
}

long long query_y(int kx, int ky, int left, int right, int levo_kol, int desno_kol) {
    if (m<=2000) {
        if (left>=levo_kol && right<=desno_kol)
            return tree[kx][ky];
        else if (left>desno_kol || right<levo_kol)
            return 0;
        int mid=(left+right)/2;
        long long r1=query_y(kx, 2*ky, left, mid, levo_kol, desno_kol);
        long long r2=query_y(kx, 2*ky+1, mid+1, right, levo_kol, desno_kol);
        return nzd(r1, r2);
    }
    else {
        if (left>=levo_kol && right<=desno_kol)
            return tree2[kx][ky];
        else if (left>desno_kol || right<levo_kol)
            return 0;
        int mid=(left+right)/2;
        long long r1=query_y(kx, 2*ky, left, mid, levo_kol, desno_kol);
        long long r2=query_y(kx, 2*ky+1, mid+1, right, levo_kol, desno_kol);
        return nzd(r1, r2);
    }
}

long long query_x(int k, int left, int right, int gore_red, int dole_red, int levo_kol, int desno_kol) {
    if (left>=gore_red && right<=dole_red)
        return query_y(k, 1, 0, m-1, levo_kol, desno_kol);
    else if (left>dole_red || right<gore_red)
        return 0;
    int mid=(left+right)/2;
    long long r1=query_x(2*k, left, mid, gore_red, dole_red, levo_kol, desno_kol);
    long long r2=query_x(2*k+1, mid+1, right, gore_red, dole_red, levo_kol, desno_kol);
    return nzd(r1, r2);
}

void update_y(int kx, int left_x, int right_x, int ky, int left_y, int right_y, int row, int col, long long val) {
    if (m<=2000) {
        if (left_y==right_y) {
            if (left_x==right_x)
                tree[kx][ky]=val;
            else
                tree[kx][ky]=nzd(tree[2*kx][ky], tree[2*kx+1][ky]);
        }
        else {
            int mid=(left_y+right_y)/2;
            if (col>mid)
                update_y(kx, left_x, right_x, 2*ky+1, mid+1, right_y, row, col, val);
            else
                update_y(kx, left_x, right_x, 2*ky, left_y, mid, row, col, val);
            tree[kx][ky]=nzd(tree[kx][2*ky], tree[kx][2*ky+1]);
        }
    }
    else {
        if (left_y==right_y) {
            if (left_x==right_x)
                tree2[kx][ky]=val;
            else
                tree2[kx][ky]=nzd(tree2[2*kx][ky], tree2[2*kx+1][ky]);
        }
        else {
            int mid=(left_y+right_y)/2;
            if (col>mid)
                update_y(kx, left_x, right_x, 2*ky+1, mid+1, right_y, row, col, val);
            else
                update_y(kx, left_x, right_x, 2*ky, left_y, mid, row, col, val);
            tree2[kx][ky]=nzd(tree2[kx][2*ky], tree2[kx][2*ky+1]);
        }
    }
}

void update_x(int k, int left, int right, int row, int col, long long val) {
    if (left!=right) {
        int mid=(left+right)/2;
        if (row>mid) update_x(2*k+1, mid+1, right, row, col, val);
        else update_x(2*k, left, mid, row, col, val);
    }
    update_y(k, left, right, 1, 0, m-1, row, col, val);
}

void init(int r, int c) {
    n=r, m=c;
}

void update(int r, int c, long long br) {
    update_x(1, 0, n-1, r, c, br);
}

long long calculate(int x1, int y1, int x2, int y2) {
    long long rez=query_x(1, 0, n-1, x1, x2, y1, y2);
    return rez;
}

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