oj.uz

Submission #24117

# Submission time Handle Problem Language Result Execution time Memory
24117 2017-05-31T10:37:48 Z Mamnoon_Siam Game (IOI13_game) C++14
37 / 100
 6593 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;

unordered_map<long long, unordered_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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2032 KB Output is correct
2 Correct 6 ms 4012 KB Output is correct
3 Correct 6 ms 4012 KB Output is correct
4 Correct 0 ms 2032 KB Output is correct
5 Correct 6 ms 4012 KB Output is correct
6 Correct 6 ms 4012 KB Output is correct
7 Correct 0 ms 2164 KB Output is correct
8 Correct 0 ms 2560 KB Output is correct
9 Correct 9 ms 4012 KB Output is correct
10 Correct 6 ms 4012 KB Output is correct
11 Correct 6 ms 4012 KB Output is correct
12 Correct 0 ms 2032 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory 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 4066 ms 158876 KB Output is correct
5 Correct 2906 ms 158876 KB Output is correct
6 Correct 4169 ms 158876 KB Output is correct
7 Correct 4536 ms 158876 KB Output is correct
8 Correct 3469 ms 158876 KB Output is correct
9 Correct 3979 ms 158876 KB Output is correct
10 Correct 3736 ms 158876 KB Output is correct
11 Correct 0 ms 2032 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2032 KB Output is correct
2 Correct 3 ms 4012 KB Output is correct
3 Correct 6 ms 4012 KB Output is correct
4 Correct 0 ms 2032 KB Output is correct
5 Correct 6 ms 4012 KB Output is correct
6 Correct 9 ms 4012 KB Output is correct
7 Correct 0 ms 2164 KB Output is correct
8 Correct 0 ms 2560 KB Output is correct
9 Correct 13 ms 4012 KB Output is correct
10 Correct 6 ms 4012 KB Output is correct
11 Correct 6 ms 4012 KB Output is correct
12 Correct 4973 ms 185584 KB Output is correct
13 Correct 6506 ms 185584 KB Output is correct
14 Memory limit exceeded 903 ms 256000 KB Memory limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2032 KB Output is correct
2 Correct 13 ms 4012 KB Output is correct
3 Correct 9 ms 4012 KB Output is correct
4 Correct 0 ms 2032 KB Output is correct
5 Correct 9 ms 4012 KB Output is correct
6 Correct 13 ms 4012 KB Output is correct
7 Correct 0 ms 2164 KB Output is correct
8 Correct 3 ms 2560 KB Output is correct
9 Correct 9 ms 4012 KB Output is correct
10 Correct 9 ms 4012 KB Output is correct
11 Correct 13 ms 4012 KB Output is correct
12 Correct 5196 ms 158876 KB Output is correct
13 Correct 2993 ms 158876 KB Output is correct
14 Correct 4103 ms 158876 KB Output is correct
15 Correct 4236 ms 158876 KB Output is correct
16 Correct 3766 ms 158876 KB Output is correct
17 Correct 4513 ms 158876 KB Output is correct
18 Correct 4326 ms 158876 KB Output is correct
19 Correct 5449 ms 185584 KB Output is correct
20 Correct 6593 ms 185584 KB Output is correct
21 Memory limit exceeded 976 ms 256000 KB Memory limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2032 KB Output is correct
2 Correct 9 ms 4012 KB Output is correct
3 Correct 6 ms 4012 KB Output is correct
4 Correct 0 ms 2032 KB Output is correct
5 Correct 9 ms 4012 KB Output is correct
6 Correct 9 ms 4012 KB Output is correct
7 Correct 0 ms 2164 KB Output is correct
8 Correct 3 ms 2560 KB Output is correct
9 Correct 3 ms 4012 KB Output is correct
10 Correct 9 ms 4012 KB Output is correct
11 Correct 13 ms 4012 KB Output is correct
12 Correct 5389 ms 158876 KB Output is correct
13 Correct 3266 ms 158876 KB Output is correct
14 Correct 4546 ms 158876 KB Output is correct
15 Correct 4159 ms 158876 KB Output is correct
16 Correct 3969 ms 158876 KB Output is correct
17 Correct 4636 ms 158876 KB Output is correct
18 Correct 4186 ms 158876 KB Output is correct
19 Correct 5336 ms 185584 KB Output is correct
20 Correct 6533 ms 185584 KB Output is correct
21 Memory limit exceeded 1033 ms 256000 KB Memory limit exceeded
22 Halted 0 ms 0 KB -