| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 24080 |
2017-05-30T11:24:00 Z |
Mamnoon_Siam |
Game (IOI13_game) |
C++14 |
|
1143 ms |
134636 KB |
#include <bits/stdc++.h>
using namespace std;
#ifndef __GAME_H__
#define __GAME_H__
#ifdef __cplusplus
extern "C" {
#endif
const long long maxn=2060;
long long tree[maxn*2][maxn*2]; 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, 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(long long i=0; i<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;
^
game.cpp: In function 'void update_row(long long int, long long int, long long int, long long int, long long int, long long int)':
game.cpp:73:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(long long i=0; i<edit.size(); i++) tree[node][edit[i]]=gcd(tree[left][edit[i]], tree[right][edit[i]]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
134636 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
134636 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
134636 KB |
Output is correct |
| 2 |
Correct |
0 ms |
134636 KB |
Output is correct |
| 3 |
Correct |
0 ms |
134636 KB |
Output is correct |
| 4 |
Incorrect |
1143 ms |
134636 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
134636 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
134636 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
134636 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
134636 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
134636 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
134636 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
