답안 #24120 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
24120	2017-05-31T10:46:55 Z	Mamnoon_Siam	게임 (IOI13_game)	C++14	36 / 100	3406 ms	229836 KB

game

#include <bits/stdc++.h>
using namespace std;

#ifndef __GAME_H__
#define __GAME_H__

#ifdef __cplusplus
extern "C" {
#endif

const long long maxn=2700;

long long tree[maxn*2][maxn*2]; long long maxR, maxC;
vector<long long> edit;

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;
}

void build_merge(long long parent, long long left, long long right, long long node, long long b, long long e)
{
    if(b==e) { tree[parent][node] = gcd(tree[left][node], tree[right][node]); return ; }
    long long __left=node<<1; long long __right=__left+1; long long mid=(b+e)>>1;
    build_merge(parent, left, right, __left, b, mid);
    build_merge(parent, left, right, __right, mid+1, e);
    tree[parent][node]=gcd(tree[left][node], tree[right][node]);
}

void build_col(long long row, long long node, long long b, long long e)
{
    if(b==e) { tree[row][node] = (long long)0; return ; }
    long long left=node<<1; long long right=left+1; long long mid=(b+e)>>1;
    build_col(row, left, b, mid); build_col(row, right, mid+1, e);
    tree[row][node]=gcd(tree[row][left], tree[row][right]);
}

void build_row(long long node, long long b, long long e)
{
    if(b==e) { build_col(node, 1, 0, maxC-1); return ; }
    long long left=node<<1; long long right=left+1; long long mid=(b+e)>>1;
    build_row(left, b, mid); build_row(right, mid+1, e);
    build_merge(node, left, right, 1, 0, maxC-1);
}

void make_update_merge_list(long long node, long long b, long long e, long long pos)
{
    if(b>pos || e<pos) return ; edit.push_back(node); if(b==e) return ;
    long long left=node<<1; long long right=left+1; long long mid=(b+e)>>1;
    make_update_merge_list(left, b, mid, pos); make_update_merge_list(right, mid+1, e, pos);
}

void update_col(long long row, long long node, long long b, long long e, long long pos, long long val)
{
    if(b>pos || e<pos) return ;
    if(b==e) { tree[row][node]=val; return ; }
    long long left=node<<1; long long right=left+1; long long mid=(b+e)>>1;
    update_col(row, left, b, mid, pos, val); update_col(row, right, mid+1, e, pos, val);
    tree[row][node]=gcd(tree[row][left], tree[row][right]);
}

void update_row(long long node, long long b, long long e, long long x, long long y, long long val)
{
    if(b>x || e<x) return ;
    if(b==e) { update_col(node, 1, 0, maxC-1, y, val); return ; }
    long long left=node<<1; long long right=left+1; long long mid=(b+e)>>1;
    update_row(left, b, mid, x, y, val); update_row(right, mid+1, e, x, y, val);
    for(int i=0; i<(int)edit.size(); i++) tree[node][edit[i]]=gcd(tree[left][edit[i]], tree[right][edit[i]]);
}

long long calculate_col(long long row, long long node, long long b, long long e, long long i, long long j)
{
    if(b>j || e<i) return (long long)0;
    if(i<=b && e<=j) return tree[row][node];
    long long left=node<<1; long long right=left+1; long long mid=(b+e)>>1;
    return gcd(calculate_col(row, left, b, mid, i, j), calculate_col(row, right, mid+1, e, i ,j));
}

long long calculate_row(long long node, long long b, long long e, long long i, long long j, long long l, long long r)
{
    if(b>j || e<i) return (long long)0;
    if(i<=b && e<=j) return calculate_col(node, 1, 0, maxC-1, l , r);
    long long left=node<<1; long long right=left+1; long long mid=(b+e)>>1;
    return gcd(calculate_row(left, b, mid, i, j, l, r), calculate_row(right, mid+1, e, i, j, l, r));
}

void init(long long R, long long C)
{
    maxR=R; maxC=C;
    build_row(1, 0, maxR-1);
}
void update(long long P, long long Q, long long K)
{
    edit.clear();
    make_update_merge_list(1, 0, maxC-1, Q);
    update_row(1, 0, maxR-1, P, Q, K);
}
long long calculate(long long P, long long Q, long long U, long long V)
{
     return calculate_row(1, 0, maxR-1, P, U, Q, V);
}

#ifdef __cplusplus
}
#endif

#endif /* __GAME_H__ */

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

Subtask #2
0 / 27.0

#	결과	실행 시간	메모리	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	1106 ms	229836 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	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	1466 ms	229836 KB	Output is correct
13	Correct	2639 ms	229836 KB	Output is correct
14	Correct	1143 ms	229836 KB	Output is correct
15	Correct	3406 ms	229836 KB	Output is correct
16	Correct	343 ms	229836 KB	Output is correct
17	Correct	2406 ms	229836 KB	Output is correct
18	Correct	2773 ms	229836 KB	Output is correct
19	Correct	2519 ms	229836 KB	Output is correct
20	Correct	2249 ms	229836 KB	Output is correct
21	Correct	0 ms	229836 KB	Output is correct

Subtask #4
0 / 17.0

#	결과	실행 시간	메모리	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	946 ms	229836 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	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	1053 ms	229836 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

답안 #24120

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 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
0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
0 / 17.0

Subtask #5
0 / 20.0