oj.uz

Submission #24324

# Submission time Handle Problem Language Result Execution time Memory
24324 2017-06-05T11:07:59 Z Mamnoon_Siam Game (IOI13_game) C++14
37 / 100
 6336 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; //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 2032 KB Output is correct
2 Correct 6 ms 4012 KB Output is correct
3 Correct 3 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 13 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 9 ms 4012 KB Output is correct
11 Correct 3 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 5599 ms 158876 KB Output is correct
5 Correct 3556 ms 158876 KB Output is correct
6 Correct 4373 ms 158876 KB Output is correct
7 Correct 4303 ms 158876 KB Output is correct
8 Correct 4116 ms 158876 KB Output is correct
9 Correct 4149 ms 158876 KB Output is correct
10 Correct 4339 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 9 ms 4012 KB Output is correct
3 Correct 3 ms 4012 KB Output is correct
4 Correct 0 ms 2032 KB Output is correct
5 Correct 13 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 6 ms 4012 KB Output is correct
10 Correct 9 ms 4012 KB Output is correct
11 Correct 9 ms 4012 KB Output is correct
12 Correct 5443 ms 185584 KB Output is correct
13 Correct 5709 ms 185584 KB Output is correct
14 Memory limit exceeded 1043 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 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 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 9 ms 4012 KB Output is correct
10 Correct 9 ms 4012 KB Output is correct
11 Correct 9 ms 4012 KB Output is correct
12 Correct 4863 ms 158876 KB Output is correct
13 Correct 3463 ms 158876 KB Output is correct
14 Correct 4819 ms 158876 KB Output is correct
15 Correct 4479 ms 158876 KB Output is correct
16 Correct 4009 ms 158876 KB Output is correct
17 Correct 4379 ms 158876 KB Output is correct
18 Correct 4243 ms 158876 KB Output is correct
19 Correct 5006 ms 185584 KB Output is correct
20 Correct 5873 ms 185584 KB Output is correct
21 Memory limit exceeded 1033 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 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 3 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 9 ms 4012 KB Output is correct
10 Correct 9 ms 4012 KB Output is correct
11 Correct 9 ms 4012 KB Output is correct
12 Correct 5129 ms 158876 KB Output is correct
13 Correct 3266 ms 158876 KB Output is correct
14 Correct 4159 ms 158876 KB Output is correct
15 Correct 4539 ms 158876 KB Output is correct
16 Correct 4053 ms 158876 KB Output is correct
17 Correct 4796 ms 158876 KB Output is correct
18 Correct 4743 ms 158876 KB Output is correct
19 Correct 5406 ms 185584 KB Output is correct
20 Correct 6336 ms 185584 KB Output is correct
21 Memory limit exceeded 1056 ms 256000 KB Memory limit exceeded
22 Halted 0 ms 0 KB -