oj.uz

Submission #24348

# Submission time Handle Problem Language Result Execution time Memory
24348 2017-06-05T16:20:07 Z Mamnoon_Siam Game (IOI13_game) C++14
0 / 100
 3 ms 2428 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 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);
    if(tree[row].find(left) != tree[row].end()) tree[row][node]=tree[row][left];
    if(tree[row].find(right)!= tree[row].end()) tree[row][node]=gcd(tree[row][node], 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++) {
        if(tree.find(left) != tree.end()) tree[node][edit[i]]=tree[left][edit[i]];
        if(tree.find(right)!= tree.end()) tree[node][edit[i]]=gcd(tree[node][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(tree.find(row) == tree.end()) return 0;
    if(b>j || e<i) return (long long)0;
    if(i<=b && e<=j) return ((tree[row].find(node) != tree[row].end()) ? tree[row][node] : 0);
    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);
}
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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2032 KB Output is correct
2 Correct 3 ms 2428 KB Output is correct
3 Correct 3 ms 2428 KB Output is correct
4 Incorrect 0 ms 2032 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2032 KB Output is correct
2 Incorrect 0 ms 2032 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2032 KB Output is correct
2 Correct 3 ms 2428 KB Output is correct
3 Correct 3 ms 2428 KB Output is correct
4 Incorrect 0 ms 2032 KB Output isn't correct
5 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 3 ms 2428 KB Output is correct
3 Correct 3 ms 2428 KB Output is correct
4 Incorrect 0 ms 2032 KB Output isn't correct
5 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 3 ms 2428 KB Output is correct
3 Correct 3 ms 2428 KB Output is correct
4 Incorrect 0 ms 2032 KB Output isn't correct
5 Halted 0 ms 0 KB -