Submission #1091137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091137		kkkkkkkk	Game (IOI13_game)	C++14	37 / 100	821 ms	256000 KiB

game

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

using namespace std;

long long n, m;
vector<vector<long long> > tree;

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

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 (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]);
    }
}

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) {
    tree.resize(4*r, vector<long long> (4*c, 0));
    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;
}
/*
int main()
{
    init(2, 3);
    update(0, 0, 20);
    update(0, 2, 15);
    update(1, 1, 12);
    cout << calculate(0, 0, 0, 2) << endl;
    cout << calculate(0, 0, 1, 1) << endl;
    update(0, 1, 6);
    update(1, 1, 14);
    cout << calculate(0, 0, 0, 2) << endl;
    cout << calculate(0, 0, 1, 1) << endl;

    return 0;
}
*/

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