oj.uz

답안 #24121

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
24121 2017-05-31T10:49:43 Z Mamnoon_Siam 게임 (IOI13_game) C++14
37 / 100
 13000 ms 256000 KB 
#include <bits/stdc++.h>
using namespace std;

#ifndef __GAME_H__
#define __GAME_H__

#ifdef __cplusplus
extern "C" {
#endif

const long long maxn=2700;

map<long long, map<long long, long long> > tree; 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 0 ms 2032 KB Output is correct
2 Correct 13 ms 4540 KB Output is correct
3 Correct 13 ms 4540 KB Output is correct
4 Correct 0 ms 2032 KB Output is correct
5 Correct 9 ms 4540 KB Output is correct
6 Correct 13 ms 4540 KB Output is correct
7 Correct 0 ms 2164 KB Output is correct
8 Correct 3 ms 2824 KB Output is correct
9 Correct 13 ms 4540 KB Output is correct
10 Correct 9 ms 4540 KB Output is correct
11 Correct 6 ms 4540 KB Output is correct
12 Correct 0 ms 2032 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2032 KB Output is correct
2 Correct 0 ms 2032 KB Output is correct
3 Correct 0 ms 2164 KB Output is correct
4 Correct 11129 ms 239500 KB Output is correct
5 Correct 8616 ms 239500 KB Output is correct
6 Correct 11263 ms 239500 KB Output is correct
7 Correct 10613 ms 239500 KB Output is correct
8 Correct 9646 ms 239500 KB Output is correct
9 Correct 10856 ms 239500 KB Output is correct
10 Correct 10956 ms 239500 KB Output is correct
11 Correct 0 ms 2032 KB Output is correct

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2032 KB Output is correct
2 Correct 13 ms 4540 KB Output is correct
3 Correct 13 ms 4540 KB Output is correct
4 Correct 0 ms 2032 KB Output is correct
5 Correct 6 ms 4540 KB Output is correct
6 Correct 13 ms 4540 KB Output is correct
7 Correct 0 ms 2164 KB Output is correct
8 Correct 3 ms 2824 KB Output is correct
9 Correct 13 ms 4540 KB Output is correct
10 Correct 9 ms 4540 KB Output is correct
11 Correct 9 ms 4540 KB Output is correct
12 Correct 12573 ms 252040 KB Output is correct
13 Correct 12556 ms 252040 KB Output is correct
14 Memory limit exceeded 1313 ms 256000 KB Memory limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2032 KB Output is correct
2 Correct 16 ms 4540 KB Output is correct
3 Correct 16 ms 4540 KB Output is correct
4 Correct 0 ms 2032 KB Output is correct
5 Correct 13 ms 4540 KB Output is correct
6 Correct 13 ms 4540 KB Output is correct
7 Correct 0 ms 2164 KB Output is correct
8 Correct 3 ms 2824 KB Output is correct
9 Correct 16 ms 4540 KB Output is correct
10 Correct 13 ms 4540 KB Output is correct
11 Correct 9 ms 4540 KB Output is correct
12 Correct 12476 ms 239500 KB Output is correct
13 Correct 8009 ms 239500 KB Output is correct
14 Correct 10649 ms 239500 KB Output is correct
15 Correct 9906 ms 239500 KB Output is correct
16 Correct 8646 ms 239500 KB Output is correct
17 Correct 10326 ms 239500 KB Output is correct
18 Correct 10219 ms 239500 KB Output is correct
19 Correct 12353 ms 252040 KB Output is correct
20 Correct 12566 ms 252040 KB Output is correct
21 Memory limit exceeded 1373 ms 256000 KB Memory limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2032 KB Output is correct
2 Correct 13 ms 4540 KB Output is correct
3 Correct 13 ms 4540 KB Output is correct
4 Correct 0 ms 2032 KB Output is correct
5 Correct 13 ms 4540 KB Output is correct
6 Correct 16 ms 4540 KB Output is correct
7 Correct 0 ms 2164 KB Output is correct
8 Correct 3 ms 2824 KB Output is correct
9 Correct 19 ms 4540 KB Output is correct
10 Correct 9 ms 4540 KB Output is correct
11 Correct 9 ms 4540 KB Output is correct
12 Correct 12986 ms 239500 KB Output is correct
13 Correct 8396 ms 239500 KB Output is correct
14 Correct 10696 ms 239500 KB Output is correct
15 Correct 10923 ms 239500 KB Output is correct
16 Correct 8169 ms 239500 KB Output is correct
17 Correct 9639 ms 239500 KB Output is correct
18 Correct 9569 ms 239500 KB Output is correct
19 Execution timed out 13000 ms 252040 KB Execution timed out
20 Halted 0 ms 0 KB -