Submission #24043

# Submission time Handle Problem Language Result Execution time Memory
24043 2017-05-29T23:01:57 Z RezwanArefin01 Game (IOI13_game) C++14
0 / 100
0 ms 956 KB
#include "game.h"

long long gcd(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
const int maxn = 2010;
long long tree[4*maxn][4*maxn], n, m;
void updateY(int ndx, int lx, int rx, int ndy, int ly, int ry, int y, int val) {
    if(ly == ry) {
        if(lx == rx) tree[ndx][ndy] = val;
        else tree[ndx][ndy] = gcd(tree[ndx*2][ndy], tree[ndx*2+1][ndy]);
        return;
    } int mid = ly + ry >> 1;
    if(y <= mid) updateY(ndx, lx, rx, ndy*2, ly, mid, y, val);
    else updateY(ndx, lx, rx, ndy*2+1, mid+1, ly, y, val); 
    tree[ndx][ndy] = gcd(tree[ndx][ndy*2], tree[ndx][ndy*2+1]);
}
void updateX(int ndx, int lx, int rx, int x, int y, int val) {
    if(lx != rx) {
        int mid = lx + rx >> 1;
        if(x <= mid) updateX(ndx*2, lx, mid, x, y, val);
        else updateX(ndx*2+1, mid+1, rx, x,y, val);
    } updateY(ndx, lx, rx, 1, 0, m-1, y,val);
}

long long queryY(int ndx, int ndy, int ly, int ry, int y1, int y2) {
    if(ry < y1 || ly > y2) return 0;
    if(y1 <= ly && ry <= y2) 
        return tree[ndx][ndy];
    int mid = ly + ry >> 1;
    return gcd(queryY(ndx, ndy*2, ly, mid, y1, y2), 
           queryY(ndx, ndy*2+1, mid+1, ry, y1, y2));
}
long long queryX(int ndx, int lx, int rx, int x1, int y1, int x2, int y2) {
    if(rx < x1 || lx > x2) return 0;
    if(x1 <= lx && rx <= x2) {
        return queryY(ndx, 1, 0, m-1, y1, y2);
    } int mid = lx + rx >> 1;
    return gcd(queryX(ndx*2, lx, mid, x1,y1,x2,y2),
           queryX(ndx*2+1, mid+1, rx, x1,y1,x2,y2));
}

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

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

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

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^
game.cpp: In function 'void updateY(int, int, int, int, int, int, int, int)':
game.cpp:19:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     } int mid = ly + ry >> 1;
                    ^
game.cpp: In function 'void updateX(int, int, int, int, int, int)':
game.cpp:26:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = lx + rx >> 1;
                      ^
game.cpp: In function 'long long int queryY(int, int, int, int, int, int)':
game.cpp:36:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = ly + ry >> 1;
                  ^
game.cpp: In function 'long long int queryX(int, int, int, int, int, int, int)':
game.cpp:44:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     } int mid = lx + rx >> 1;
                    ^
# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 956 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 956 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 956 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 956 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 956 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -