oj.uz

Submission #24226

# Submission time Handle Problem Language Result Execution time Memory
24226 2017-06-02T17:21:21 Z Parthib_Gupta Game (IOI13_game) C++14
10 / 100
 0 ms 3272 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[4 * 100][4 * 100];


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 3272 KB Output is correct
2 Correct 0 ms 3272 KB Output is correct
3 Correct 0 ms 3272 KB Output is correct
4 Correct 0 ms 3272 KB Output is correct
5 Correct 0 ms 3272 KB Output is correct
6 Correct 0 ms 3272 KB Output is correct
7 Correct 0 ms 3272 KB Output is correct
8 Correct 0 ms 3272 KB Output is correct
9 Correct 0 ms 3272 KB Output is correct
10 Correct 0 ms 3272 KB Output is correct
11 Correct 0 ms 3272 KB Output is correct
12 Correct 0 ms 3272 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3272 KB Output is correct
2 Correct 0 ms 3272 KB Output is correct
3 Correct 0 ms 3272 KB Output is correct
4 Runtime error 0 ms 3272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3272 KB Output is correct
2 Correct 0 ms 3272 KB Output is correct
3 Correct 0 ms 3272 KB Output is correct
4 Correct 0 ms 3272 KB Output is correct
5 Correct 0 ms 3272 KB Output is correct
6 Correct 0 ms 3272 KB Output is correct
7 Correct 0 ms 3272 KB Output is correct
8 Correct 0 ms 3272 KB Output is correct
9 Correct 0 ms 3272 KB Output is correct
10 Correct 0 ms 3272 KB Output is correct
11 Correct 0 ms 3272 KB Output is correct
12 Runtime error 0 ms 3272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3272 KB Output is correct
2 Correct 0 ms 3272 KB Output is correct
3 Correct 0 ms 3272 KB Output is correct
4 Correct 0 ms 3272 KB Output is correct
5 Correct 0 ms 3272 KB Output is correct
6 Correct 0 ms 3272 KB Output is correct
7 Correct 0 ms 3272 KB Output is correct
8 Correct 0 ms 3272 KB Output is correct
9 Correct 0 ms 3272 KB Output is correct
10 Correct 0 ms 3272 KB Output is correct
11 Correct 0 ms 3272 KB Output is correct
12 Runtime error 0 ms 3272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3272 KB Output is correct
2 Correct 0 ms 3272 KB Output is correct
3 Correct 0 ms 3272 KB Output is correct
4 Correct 0 ms 3272 KB Output is correct
5 Correct 0 ms 3272 KB Output is correct
6 Correct 0 ms 3272 KB Output is correct
7 Correct 0 ms 3272 KB Output is correct
8 Correct 0 ms 3272 KB Output is correct
9 Correct 0 ms 3272 KB Output is correct
10 Correct 0 ms 3272 KB Output is correct
11 Correct 0 ms 3272 KB Output is correct
12 Runtime error 0 ms 3272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -