답안 #24232 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
24232	2017-06-02T19:37:22 Z	Parthib_Gupta	게임 (IOI13_game)	C++14	63 / 100	3509 ms	197608 KB

game

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #24232

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 0 / 17.0

Subtask #5 0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
0 / 17.0

Subtask #5
0 / 20.0