oj.uz

Submission #24048

# Submission time Handle Problem Language Result Execution time Memory
24048 2017-05-29T23:15:34 Z RezwanArefin01 Game (IOI13_game) C++14
0 / 100
 0 ms 2664 KB 
#include "game.h"
#include <assert.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 = 111;
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, long long 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, long long 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) {
    assert(R == 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, long long int)':
game.cpp:20:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     } int mid = ly + ry >> 1;
                    ^
game.cpp: In function 'void updateX(int, int, int, int, int, long long int)':
game.cpp:27: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:37: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:45:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     } int mid = lx + rx >> 1;
                    ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2660 KB Output is correct
2 Incorrect 0 ms 2660 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2660 KB Output is correct
2 Runtime error 0 ms 2664 KB Execution killed because of forbidden syscall gettid (186)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2660 KB Output is correct
2 Incorrect 0 ms 2660 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2660 KB Output is correct
2 Incorrect 0 ms 2660 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2660 KB Output is correct
2 Incorrect 0 ms 2660 KB Output isn't correct
3 Halted 0 ms 0 KB -