oj.uz

Submission #24229

# Submission time Handle Problem Language Result Execution time Memory
24229 2017-06-02T17:43:01 Z Parthib_Gupta Game (IOI13_game) C++14
36 / 100
 3256 ms 229836 KB 
#include "game.h"
#include "bits/stdc++.h"

typedef long long vlong;
long long gcd2(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 r , c ;
long long tree[2700 * 2][2 * 2700];


vlong qy(vlong ndx, vlong ndy, vlong st, vlong ed,vlong y1,vlong y2)
{
    if(y2 < st || y1 > ed)
        return 0;
    if(y2 >= ed && y1 <= st){
        return tree[ndx][ndy];
    }
    vlong md = (st+ed)/2;
    vlong v1 = qy(ndx, 2*ndy, st, md, y1, y2);
    vlong v2 = qy(ndx, 2*ndy + 1, md+ 1, ed, y1, y2);

    return gcd2(v1, v2);
}
vlong qx(vlong nd, vlong st, vlong ed, vlong x1, vlong y1, vlong x2, vlong y2)
{
    if(ed < x1 || st > x2)
        return 0;

    if(x1 <= st && ed <= x2){
        return qy(nd, 1, 0, c-1, y1, y2);
    }

    vlong md = (st+ed)/2;
    vlong v1 = qx(2*nd, st, md, x1, y1, x2, y2);
    vlong v2 = qx(2*nd + 1, md+1, ed, x1, y1, x2, y2);
    return gcd2(v1, v2);

}

void up_y(vlong ndx, vlong lx, vlong rx, vlong nd, vlong st, vlong ed, vlong y, vlong nVal)
{
    if(st == ed){
        if(lx == rx){
            tree[ndx][nd] = nVal;
        }
        else{
            tree[ndx][nd] = gcd2(tree[ndx*2][nd], tree[ndx*2 + 1][nd]);
        }
        return;
    }

    vlong md = (st+ed)/2;
    if(y <= md)
        up_y(ndx, lx, rx, nd*2, st, md, y, nVal);
    else
        up_y(ndx, lx, rx, nd*2 + 1, md + 1, ed, y, nVal);

    tree[ndx][nd] = gcd2(tree[ndx][nd*2], tree[ndx][nd*2 + 1]);
}

void up_x(vlong nd, vlong st, vlong ed, vlong x, vlong y, vlong nVal)
{
   // cerr << "I am here\n";
    if(st != ed){
        vlong md = (st+ed)/2;
        if(x <= md) up_x(2*nd, st, md, x, y, nVal);
        else up_x(2*nd + 1, md+1, ed, x, y, nVal);
    }
    up_y(nd, st, ed, 1, 0, c-1, y, nVal);
}

void build_Y(vlong nx, vlong sx, vlong ex, vlong nd, vlong st, vlong ed)
{
    
    if(st == ed){
        if(sx == ex){
            tree[nx][nd] = 0;
        }
        else{
            tree[nx][nd] = gcd2(tree[nx*2][nd], tree[nx*2 + 1][nd]);
        }
        return;
    }
    vlong md = (st+ed)/2;
    build_Y(nx, sx, ex, 2*nd, st, md);
    build_Y(nx, sx, ex, 2*nd + 1, md+1, ed);
    tree[nx][nd] = gcd2(tree[nx][2*nd], tree[nx][2*nd + 1]);
}

void build_X(vlong nd, vlong st, vlong ed)
{

    if(st != ed){
        vlong md = (st+ed)/2;
        build_X(2*nd, st, md);
        build_X(2*nd + 1, md + 1, ed);
    }

    build_Y(nd, st, ed, 1, 0, c-1);
}

void init(int R, int C) {
    r = R;
    c = C;
    build_X(1, 0, R-1);
}

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

long long calculate(int P, int Q, int U, int V) {
    return qx(1, 0, r-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;
      ^

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 229836 KB Output is correct
2 Correct 0 ms 229836 KB Output is correct
3 Correct 0 ms 229836 KB Output is correct
4 Incorrect 986 ms 229836 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 229836 KB Output is correct
2 Correct 0 ms 229836 KB Output is correct
3 Correct 0 ms 229836 KB Output is correct
4 Correct 0 ms 229836 KB Output is correct
5 Correct 0 ms 229836 KB Output is correct
6 Correct 0 ms 229836 KB Output is correct
7 Correct 0 ms 229836 KB Output is correct
8 Correct 0 ms 229836 KB Output is correct
9 Correct 0 ms 229836 KB Output is correct
10 Correct 0 ms 229836 KB Output is correct
11 Correct 0 ms 229836 KB Output is correct
12 Correct 1513 ms 229836 KB Output is correct
13 Correct 2613 ms 229836 KB Output is correct
14 Correct 943 ms 229836 KB Output is correct
15 Correct 3256 ms 229836 KB Output is correct
16 Correct 373 ms 229836 KB Output is correct
17 Correct 1923 ms 229836 KB Output is correct
18 Correct 2216 ms 229836 KB Output is correct
19 Correct 1993 ms 229836 KB Output is correct
20 Correct 2176 ms 229836 KB Output is correct
21 Correct 0 ms 229836 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 229836 KB Output is correct
2 Correct 0 ms 229836 KB Output is correct
3 Correct 0 ms 229836 KB Output is correct
4 Correct 0 ms 229836 KB Output is correct
5 Correct 0 ms 229836 KB Output is correct
6 Correct 0 ms 229836 KB Output is correct
7 Correct 0 ms 229836 KB Output is correct
8 Correct 0 ms 229836 KB Output is correct
9 Correct 0 ms 229836 KB Output is correct
10 Correct 0 ms 229836 KB Output is correct
11 Correct 0 ms 229836 KB Output is correct
12 Incorrect 986 ms 229836 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 229836 KB Output is correct
2 Correct 0 ms 229836 KB Output is correct
3 Correct 0 ms 229836 KB Output is correct
4 Correct 0 ms 229836 KB Output is correct
5 Correct 0 ms 229836 KB Output is correct
6 Correct 0 ms 229836 KB Output is correct
7 Correct 0 ms 229836 KB Output is correct
8 Correct 0 ms 229836 KB Output is correct
9 Correct 0 ms 229836 KB Output is correct
10 Correct 0 ms 229836 KB Output is correct
11 Correct 0 ms 229836 KB Output is correct
12 Incorrect 1103 ms 229836 KB Output isn't correct
13 Halted 0 ms 0 KB -