oj.uz

Submission #24232

# Submission time Handle Problem Language Result Execution time Memory
24232 2017-06-02T19:37:22 Z Parthib_Gupta Game (IOI13_game) C++14
63 / 100
 3509 ms 197608 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

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 ;
vector < vector <long long> > tree;


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;
    if(r <= 2000 && c <= 2000) {
        tree.resize(5000);
        for(int i=0; i<5000; i++) 
                tree[i].assign(5000, 0);
    } else {
        tree.resize(30);
        for(int i=0; i<30; i++) 
            tree[i].assign(300000, 0);
    }
    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 26 ms 197608 KB Output is correct
2 Correct 33 ms 197608 KB Output is correct
3 Correct 29 ms 197608 KB Output is correct
4 Correct 13 ms 197608 KB Output is correct
5 Correct 23 ms 197608 KB Output is correct
6 Correct 33 ms 197608 KB Output is correct
7 Correct 26 ms 197608 KB Output is correct
8 Correct 13 ms 197608 KB Output is correct
9 Correct 23 ms 197608 KB Output is correct
10 Correct 23 ms 197608 KB Output is correct
11 Correct 29 ms 197608 KB Output is correct
12 Correct 29 ms 197608 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 197608 KB Output is correct
2 Correct 13 ms 197608 KB Output is correct
3 Correct 26 ms 197608 KB Output is correct
4 Correct 1176 ms 72344 KB Output is correct
5 Correct 749 ms 72344 KB Output is correct
6 Correct 893 ms 72344 KB Output is correct
7 Correct 953 ms 72344 KB Output is correct
8 Correct 796 ms 72344 KB Output is correct
9 Correct 1059 ms 72344 KB Output is correct
10 Correct 806 ms 72344 KB Output is correct
11 Correct 36 ms 197608 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 197608 KB Output is correct
2 Correct 19 ms 197608 KB Output is correct
3 Correct 39 ms 197608 KB Output is correct
4 Correct 26 ms 197608 KB Output is correct
5 Correct 36 ms 197608 KB Output is correct
6 Correct 26 ms 197608 KB Output is correct
7 Correct 39 ms 197608 KB Output is correct
8 Correct 26 ms 197608 KB Output is correct
9 Correct 29 ms 197608 KB Output is correct
10 Correct 26 ms 197608 KB Output is correct
11 Correct 26 ms 197608 KB Output is correct
12 Correct 1449 ms 197608 KB Output is correct
13 Correct 2976 ms 197608 KB Output is correct
14 Correct 1093 ms 197608 KB Output is correct
15 Correct 3366 ms 197608 KB Output is correct
16 Correct 446 ms 197608 KB Output is correct
17 Correct 2136 ms 197608 KB Output is correct
18 Correct 2666 ms 197608 KB Output is correct
19 Correct 2399 ms 197608 KB Output is correct
20 Correct 2186 ms 197608 KB Output is correct
21 Correct 29 ms 197608 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 197608 KB Output is correct
2 Correct 39 ms 197608 KB Output is correct
3 Correct 19 ms 197608 KB Output is correct
4 Correct 26 ms 197608 KB Output is correct
5 Correct 19 ms 197608 KB Output is correct
6 Correct 33 ms 197608 KB Output is correct
7 Correct 39 ms 197608 KB Output is correct
8 Correct 29 ms 197608 KB Output is correct
9 Correct 23 ms 197608 KB Output is correct
10 Correct 19 ms 197608 KB Output is correct
11 Correct 29 ms 197608 KB Output is correct
12 Correct 1083 ms 72344 KB Output is correct
13 Correct 679 ms 72344 KB Output is correct
14 Correct 1063 ms 72344 KB Output is correct
15 Correct 933 ms 72344 KB Output is correct
16 Correct 809 ms 72344 KB Output is correct
17 Correct 1018 ms 72344 KB Output is correct
18 Correct 799 ms 72344 KB Output is correct
19 Correct 1443 ms 197608 KB Output is correct
20 Correct 2813 ms 197608 KB Output is correct
21 Correct 1126 ms 197608 KB Output is correct
22 Correct 3306 ms 197608 KB Output is correct
23 Correct 399 ms 197608 KB Output is correct
24 Correct 2129 ms 197608 KB Output is correct
25 Correct 2399 ms 197608 KB Output is correct
26 Correct 2579 ms 197608 KB Output is correct
27 Correct 2363 ms 197608 KB Output is correct
28 Runtime error 6 ms 72344 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 33 ms 197608 KB Output is correct
2 Correct 43 ms 197608 KB Output is correct
3 Correct 19 ms 197608 KB Output is correct
4 Correct 13 ms 197608 KB Output is correct
5 Correct 36 ms 197608 KB Output is correct
6 Correct 19 ms 197608 KB Output is correct
7 Correct 29 ms 197608 KB Output is correct
8 Correct 33 ms 197608 KB Output is correct
9 Correct 16 ms 197608 KB Output is correct
10 Correct 33 ms 197608 KB Output is correct
11 Correct 16 ms 197608 KB Output is correct
12 Correct 1073 ms 72344 KB Output is correct
13 Correct 686 ms 72344 KB Output is correct
14 Correct 933 ms 72344 KB Output is correct
15 Correct 979 ms 72344 KB Output is correct
16 Correct 786 ms 72344 KB Output is correct
17 Correct 916 ms 72344 KB Output is correct
18 Correct 869 ms 72344 KB Output is correct
19 Correct 1539 ms 197608 KB Output is correct
20 Correct 2899 ms 197608 KB Output is correct
21 Correct 1066 ms 197608 KB Output is correct
22 Correct 3509 ms 197608 KB Output is correct
23 Correct 453 ms 197608 KB Output is correct
24 Correct 2146 ms 197608 KB Output is correct
25 Correct 2589 ms 197608 KB Output is correct
26 Correct 2589 ms 197608 KB Output is correct
27 Correct 2399 ms 197608 KB Output is correct
28 Runtime error 6 ms 72344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -