oj.uz

Submission #24133

# Submission time Handle Problem Language Result Execution time Memory
24133 2017-05-31T11:37:31 Z Mamnoon_Siam Game (IOI13_game) C++14
63 / 100
 3289 ms 134888 KB 
#include <bits/stdc++.h>
using namespace std;

#ifndef __GAME_H__
#define __GAME_H__

#ifdef __cplusplus
extern "C" {
#endif

const long long maxn=2700;

vector<vector<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; vector<long long> temp;
    R = ((long long)ceil(log((double)R)/log(2.0)))+1; R=1<<R;
    C = ((long long)ceil(log((double)C)/log(2.0)))+1; C=1<<C;
    R+=20; C+=20;
    for(int i=0; i<C; i++) temp.push_back(0LL);
    for(int i=0; i<R; i++) tree.push_back(temp);
    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 2124 KB Output is correct
2 Correct 0 ms 2784 KB Output is correct
3 Correct 0 ms 2784 KB Output is correct
4 Correct 0 ms 2124 KB Output is correct
5 Correct 0 ms 2784 KB Output is correct
6 Correct 0 ms 2784 KB Output is correct
7 Correct 0 ms 2124 KB Output is correct
8 Correct 0 ms 2524 KB Output is correct
9 Correct 0 ms 2784 KB Output is correct
10 Correct 0 ms 2784 KB Output is correct
11 Correct 0 ms 2784 KB Output is correct
12 Correct 0 ms 2124 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2124 KB Output is correct
2 Correct 0 ms 2124 KB Output is correct
3 Correct 0 ms 2124 KB Output is correct
4 Correct 1143 ms 112808 KB Output is correct
5 Correct 749 ms 112808 KB Output is correct
6 Correct 1022 ms 112808 KB Output is correct
7 Correct 966 ms 112808 KB Output is correct
8 Correct 739 ms 112808 KB Output is correct
9 Correct 1106 ms 112808 KB Output is correct
10 Correct 866 ms 112808 KB Output is correct
11 Correct 0 ms 2124 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2124 KB Output is correct
2 Correct 0 ms 2784 KB Output is correct
3 Correct 0 ms 2784 KB Output is correct
4 Correct 0 ms 2124 KB Output is correct
5 Correct 0 ms 2784 KB Output is correct
6 Correct 0 ms 2784 KB Output is correct
7 Correct 0 ms 2124 KB Output is correct
8 Correct 0 ms 2524 KB Output is correct
9 Correct 0 ms 2784 KB Output is correct
10 Correct 0 ms 2784 KB Output is correct
11 Correct 0 ms 2784 KB Output is correct
12 Correct 1459 ms 35808 KB Output is correct
13 Correct 2743 ms 35808 KB Output is correct
14 Correct 1012 ms 134888 KB Output is correct
15 Correct 3289 ms 134888 KB Output is correct
16 Correct 383 ms 134888 KB Output is correct
17 Correct 2409 ms 134888 KB Output is correct
18 Correct 2616 ms 134888 KB Output is correct
19 Correct 2376 ms 134888 KB Output is correct
20 Correct 2593 ms 134888 KB Output is correct
21 Correct 0 ms 2124 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2124 KB Output is correct
2 Correct 0 ms 2784 KB Output is correct
3 Correct 0 ms 2784 KB Output is correct
4 Correct 0 ms 2124 KB Output is correct
5 Correct 0 ms 2784 KB Output is correct
6 Correct 0 ms 2784 KB Output is correct
7 Correct 0 ms 2124 KB Output is correct
8 Correct 0 ms 2524 KB Output is correct
9 Correct 0 ms 2784 KB Output is correct
10 Correct 0 ms 2784 KB Output is correct
11 Correct 0 ms 2784 KB Output is correct
12 Correct 1249 ms 112808 KB Output is correct
13 Correct 656 ms 112808 KB Output is correct
14 Correct 979 ms 112808 KB Output is correct
15 Correct 1006 ms 112808 KB Output is correct
16 Correct 779 ms 112808 KB Output is correct
17 Correct 1022 ms 112808 KB Output is correct
18 Correct 886 ms 112808 KB Output is correct
19 Correct 1523 ms 35808 KB Output is correct
20 Correct 2873 ms 35808 KB Output is correct
21 Correct 1289 ms 134888 KB Output is correct
22 Correct 3266 ms 134888 KB Output is correct
23 Correct 379 ms 134888 KB Output is correct
24 Correct 2203 ms 134888 KB Output is correct
25 Correct 2433 ms 134888 KB Output is correct
26 Correct 2519 ms 134888 KB Output is correct
27 Correct 2449 ms 134888 KB Output is correct
28 Runtime error 0 ms 2124 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 0 ms 2124 KB Output is correct
2 Correct 0 ms 2784 KB Output is correct
3 Correct 0 ms 2784 KB Output is correct
4 Correct 0 ms 2124 KB Output is correct
5 Correct 0 ms 2784 KB Output is correct
6 Correct 0 ms 2784 KB Output is correct
7 Correct 0 ms 2124 KB Output is correct
8 Correct 0 ms 2524 KB Output is correct
9 Correct 0 ms 2784 KB Output is correct
10 Correct 0 ms 2784 KB Output is correct
11 Correct 0 ms 2784 KB Output is correct
12 Correct 1126 ms 112808 KB Output is correct
13 Correct 696 ms 112808 KB Output is correct
14 Correct 1046 ms 112808 KB Output is correct
15 Correct 986 ms 112808 KB Output is correct
16 Correct 783 ms 112808 KB Output is correct
17 Correct 1086 ms 112808 KB Output is correct
18 Correct 1002 ms 112808 KB Output is correct
19 Correct 1589 ms 35808 KB Output is correct
20 Correct 2699 ms 35808 KB Output is correct
21 Correct 1056 ms 134888 KB Output is correct
22 Correct 3153 ms 134888 KB Output is correct
23 Correct 386 ms 134888 KB Output is correct
24 Correct 2113 ms 134888 KB Output is correct
25 Correct 2389 ms 134888 KB Output is correct
26 Correct 2539 ms 134888 KB Output is correct
27 Correct 2636 ms 134888 KB Output is correct
28 Runtime error 0 ms 2124 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -