oj.uz

Submission #24126

# Submission time Handle Problem Language Result Execution time Memory
24126 2017-05-31T11:09:35 Z RezwanArefin01 Game (IOI13_game) C++14
36 / 100
 3433 ms 132448 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 = 111;
    long long tree[4100][4100], 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, ry, 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) {
        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:19:24: 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:26:26: 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:22: 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:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         } int mid = lx + rx >> 1;
                        ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 132448 KB Output is correct
2 Correct 0 ms 132448 KB Output is correct
3 Correct 0 ms 132448 KB Output is correct
4 Correct 0 ms 132448 KB Output is correct
5 Correct 0 ms 132448 KB Output is correct
6 Correct 0 ms 132448 KB Output is correct
7 Correct 0 ms 132448 KB Output is correct
8 Correct 0 ms 132448 KB Output is correct
9 Correct 0 ms 132448 KB Output is correct
10 Correct 0 ms 132448 KB Output is correct
11 Correct 0 ms 132448 KB Output is correct
12 Correct 0 ms 132448 KB Output is correct

Subtask #2
0 / 27.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 132448 KB Output is correct
2 Correct 0 ms 132448 KB Output is correct
3 Correct 0 ms 132448 KB Output is correct
4 Correct 0 ms 132448 KB Output is correct
5 Correct 0 ms 132448 KB Output is correct
6 Correct 0 ms 132448 KB Output is correct
7 Correct 0 ms 132448 KB Output is correct
8 Correct 0 ms 132448 KB Output is correct
9 Correct 0 ms 132448 KB Output is correct
10 Correct 0 ms 132448 KB Output is correct
11 Correct 0 ms 132448 KB Output is correct
12 Correct 1483 ms 132448 KB Output is correct
13 Correct 2753 ms 132448 KB Output is correct
14 Correct 923 ms 132448 KB Output is correct
15 Correct 3433 ms 132448 KB Output is correct
16 Correct 219 ms 132448 KB Output is correct
17 Correct 2183 ms 132448 KB Output is correct
18 Correct 2576 ms 132448 KB Output is correct
19 Correct 2393 ms 132448 KB Output is correct
20 Correct 2313 ms 132448 KB Output is correct
21 Correct 0 ms 132448 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 132448 KB Output is correct
2 Correct 0 ms 132448 KB Output is correct
3 Correct 0 ms 132448 KB Output is correct
4 Correct 0 ms 132448 KB Output is correct
5 Correct 0 ms 132448 KB Output is correct
6 Correct 0 ms 132448 KB Output is correct
7 Correct 0 ms 132448 KB Output is correct
8 Correct 0 ms 132448 KB Output is correct
9 Correct 0 ms 132448 KB Output is correct
10 Correct 0 ms 132448 KB Output is correct
11 Correct 0 ms 132448 KB Output is correct
12 Incorrect 1213 ms 132448 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 132448 KB Output is correct
2 Correct 0 ms 132448 KB Output is correct
3 Correct 0 ms 132448 KB Output is correct
4 Correct 0 ms 132448 KB Output is correct
5 Correct 0 ms 132448 KB Output is correct
6 Correct 0 ms 132448 KB Output is correct
7 Correct 0 ms 132448 KB Output is correct
8 Correct 0 ms 132448 KB Output is correct
9 Correct 0 ms 132448 KB Output is correct
10 Correct 0 ms 132448 KB Output is correct
11 Correct 0 ms 132448 KB Output is correct
12 Incorrect 1293 ms 132448 KB Output isn't correct
13 Halted 0 ms 0 KB -