oj.uz

Submission #24131

# Submission time Handle Problem Language Result Execution time Memory
24131 2017-05-31T11:21:05 Z RezwanArefin01 Game (IOI13_game) C++14
63 / 100
 3573 ms 133236 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
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;
}
long long n, m;
vector< vector<long long> > tree;
 
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;
    if(n <= 2000 && m <= 2000) {
        tree.resize(4095);
        for(int i=0; i<4095; i++) 
                tree[i].assign(4095, 0);
    } else {
        tree.resize(26);
        for(int i=0; i<26; i++) 
            tree[i].assign(272141, 0);
    }
}
     
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:21: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:28: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:38: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:46:20: 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 9 ms 133236 KB Output is correct
2 Correct 26 ms 133236 KB Output is correct
3 Correct 19 ms 133236 KB Output is correct
4 Correct 29 ms 133236 KB Output is correct
5 Correct 29 ms 133236 KB Output is correct
6 Correct 6 ms 133236 KB Output is correct
7 Correct 29 ms 133236 KB Output is correct
8 Correct 33 ms 133236 KB Output is correct
9 Correct 33 ms 133236 KB Output is correct
10 Correct 19 ms 133236 KB Output is correct
11 Correct 16 ms 133236 KB Output is correct
12 Correct 16 ms 133236 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 133236 KB Output is correct
2 Correct 13 ms 133236 KB Output is correct
3 Correct 19 ms 133236 KB Output is correct
4 Correct 1006 ms 57352 KB Output is correct
5 Correct 606 ms 57352 KB Output is correct
6 Correct 916 ms 57352 KB Output is correct
7 Correct 1109 ms 57352 KB Output is correct
8 Correct 963 ms 57352 KB Output is correct
9 Correct 963 ms 57352 KB Output is correct
10 Correct 899 ms 57352 KB Output is correct
11 Correct 16 ms 133236 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 133236 KB Output is correct
2 Correct 26 ms 133236 KB Output is correct
3 Correct 16 ms 133236 KB Output is correct
4 Correct 26 ms 133236 KB Output is correct
5 Correct 26 ms 133236 KB Output is correct
6 Correct 33 ms 133236 KB Output is correct
7 Correct 19 ms 133236 KB Output is correct
8 Correct 16 ms 133236 KB Output is correct
9 Correct 16 ms 133236 KB Output is correct
10 Correct 19 ms 133236 KB Output is correct
11 Correct 33 ms 133236 KB Output is correct
12 Correct 1326 ms 133236 KB Output is correct
13 Correct 2913 ms 133236 KB Output is correct
14 Correct 1189 ms 133236 KB Output is correct
15 Correct 3249 ms 133236 KB Output is correct
16 Correct 313 ms 133236 KB Output is correct
17 Correct 2086 ms 133236 KB Output is correct
18 Correct 2663 ms 133236 KB Output is correct
19 Correct 2743 ms 133236 KB Output is correct
20 Correct 2316 ms 133236 KB Output is correct
21 Correct 13 ms 133236 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 133236 KB Output is correct
2 Correct 26 ms 133236 KB Output is correct
3 Correct 13 ms 133236 KB Output is correct
4 Correct 13 ms 133236 KB Output is correct
5 Correct 23 ms 133236 KB Output is correct
6 Correct 13 ms 133236 KB Output is correct
7 Correct 16 ms 133236 KB Output is correct
8 Correct 13 ms 133236 KB Output is correct
9 Correct 16 ms 133236 KB Output is correct
10 Correct 16 ms 133236 KB Output is correct
11 Correct 19 ms 133236 KB Output is correct
12 Correct 996 ms 57352 KB Output is correct
13 Correct 766 ms 57352 KB Output is correct
14 Correct 963 ms 57352 KB Output is correct
15 Correct 1159 ms 57352 KB Output is correct
16 Correct 879 ms 57352 KB Output is correct
17 Correct 1123 ms 57352 KB Output is correct
18 Correct 939 ms 57352 KB Output is correct
19 Correct 1369 ms 133236 KB Output is correct
20 Correct 2949 ms 133236 KB Output is correct
21 Correct 1086 ms 133236 KB Output is correct
22 Correct 3549 ms 133236 KB Output is correct
23 Correct 286 ms 133236 KB Output is correct
24 Correct 2189 ms 133236 KB Output is correct
25 Correct 2873 ms 133236 KB Output is correct
26 Correct 2663 ms 133236 KB Output is correct
27 Correct 2263 ms 133236 KB Output is correct
28 Runtime error 13 ms 57352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 133236 KB Output is correct
2 Correct 26 ms 133236 KB Output is correct
3 Correct 26 ms 133236 KB Output is correct
4 Correct 33 ms 133236 KB Output is correct
5 Correct 9 ms 133236 KB Output is correct
6 Correct 36 ms 133236 KB Output is correct
7 Correct 16 ms 133236 KB Output is correct
8 Correct 33 ms 133236 KB Output is correct
9 Correct 19 ms 133236 KB Output is correct
10 Correct 6 ms 133236 KB Output is correct
11 Correct 3 ms 133236 KB Output is correct
12 Correct 1046 ms 57352 KB Output is correct
13 Correct 706 ms 57352 KB Output is correct
14 Correct 1036 ms 57352 KB Output is correct
15 Correct 1002 ms 57352 KB Output is correct
16 Correct 883 ms 57352 KB Output is correct
17 Correct 1018 ms 57352 KB Output is correct
18 Correct 853 ms 57352 KB Output is correct
19 Correct 1509 ms 133236 KB Output is correct
20 Correct 2966 ms 133236 KB Output is correct
21 Correct 1008 ms 133236 KB Output is correct
22 Correct 3573 ms 133236 KB Output is correct
23 Correct 306 ms 133236 KB Output is correct
24 Correct 2379 ms 133236 KB Output is correct
25 Correct 2863 ms 133236 KB Output is correct
26 Correct 2669 ms 133236 KB Output is correct
27 Correct 2523 ms 133236 KB Output is correct
28 Runtime error 13 ms 57352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -