| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 7253 |
2014-07-28T14:00:45 Z |
Rhak |
Game (IOI13_game) |
C++ |
|
1376 ms |
8080 KB |
#include "game.h"
#include<stdio.h>
long long gcd2(long long x, long long y){ return y==0? x: gcd2(y, x%y); }
struct _node{
_node *d[4];
long long GCD;
_node(long long GCD):GCD(GCD){ d[0] = d[1] = d[2] = d[3] = 0; }
};
struct _IndexTree{
int S, E;
_node *root;
_IndexTree(int S,int E):S(S), E(E){ root = new _node(0);}
void update(_node* n, int s, int e, int p, long long N, _IndexTree** arr)
{
if( p < s || e < p) return;
else if( p == s && e == p){
if( N != -1) n->GCD = N;
else{
long long fn = 0;
for(int i = 0; i < 4; i++){
if(arr[i]) fn = gcd2(fn, arr[i]->read(s,e));
}
n->GCD = fn;
}
return;
}
long long t[4] = {0}, fn = 0;
for(int i = 0; i < 4; i++) t[i] = n->d[i]? n->d[i]->GCD:0;
if( e >= s+4){
int mr = ( s*3 + e) >> 2;
if( s <= p && p <= mr ){
if( !n->d[0] ) n->d[0] = new _node(0);
update(n->d[0], s, mr, p, N, arr);
t[0] = n->d[0]->GCD;
}
for(long long i = 0; i < 4; i++){
int ml = (( s*(4-i) + e*i) >> 2) + 1;
int mr = ( s*(3-i) + e*(i+1)) >> 2;
if( ml <= p && p <= mr ){
if( !n->d[i] ) n->d[i] = new _node(0);
update(n->d[i], ml, mr, p, N, arr);
t[i] = n->d[i]->GCD;
}
}
}
else{
for(int j = s, i = 0; j <= e; i++, j++){
if( j != p) continue;
if( !n->d[i] ) n->d[i] = new _node(0);
update(n->d[i], j, j, p, N, arr);
t[i] = n->d[i]->GCD;
}
}
for(int i = 0; i < 4; i ++) fn = gcd2(fn, t[i]);
n->GCD = fn;
}
void update(int p, long long N)
{
_IndexTree* arr[4] = {0};
update(root, S, E, p, N, arr);
}
void update(int p, _IndexTree** arr)
{
update(root, S, E, p, -1, arr);
}
long long read(_node *n, int s, int e, int p, int q)
{
if( !n ) return 0;
if( q < s || e < p) return 0;
else if( p <= s && e <= q){
return n->GCD;
}
int m = (s+e) >> 1;
long long t , fn = 0;
if( e >= s+4){
int mr = ( s*3 + e) >> 2;
t = n->d[0]? read(n->d[0], s, mr, p, q):0;
fn = gcd2(fn, t);
for(long long i = 1; i < 4; i++){
int ml = (( s*(4-i) + e*i) >> 2) + 1;
int mr = ( s*(3-i) + e*(i+1)) >> 2;
t = n->d[i]? read(n->d[i], ml, mr, p, q):0;
fn = gcd2(fn, t);
}
}
else{
for(int j = s, i = 0; j <= e; i++, j++){
t = n->d[i]? read(n->d[i], j, j, p, q):0;
fn = gcd2(fn, t);
}
}
return fn;
}
long long read(int s,int e){
return read(root, S, E, s, e);
}
};
struct node{
node *d[4];
_IndexTree *IT;
node(int C){
d[0] = d[1] = d[2] = d[3] = 0;
IT = new _IndexTree(0, C);
}
};
struct IndexTree{
int S, E, C;
node* root;
IndexTree(int S, int E, int C):S(S), E(E), C(C){
root = new node(C);
}
void update(node* n, int s, int e, int p, int q, long long N)
{
if( p < s || e < p) return;
if( p == s && e == p){
n->IT->update(q, N);
return;
}
long long t[4] = {0}, fn = 0;
if( e >= s+4){
int mr = ( s*3 + e) >> 2;
if( s <= p && p <= mr ){
if( !n->d[0] ) n->d[0] = new node(C);
update(n->d[0], s, mr, p, q, N);
}
for(long long i = 1; i < 4; i++){
int ml = (( s*(4-i) + e*i) >> 2) + 1;
int mr = ( s*(3-i) + e*(i+1)) >> 2;
if( ml <= p && p <= mr ){
if( !n->d[i] ) n->d[i] = new node(C);
update(n->d[i], ml, mr, p, q, N);
}
}
}
else{
for(int j = s, i = 0; j <= e; i++, j++){
if( j != p) continue;
if( !n->d[i] ) n->d[i] = new node(C);
update(n->d[i], j, j, p, q, N);
}
}
_IndexTree *arr[4] = {0};
for(int i = 0; i < 4; i++) arr[i] = n->d[i]? n->d[i]->IT: 0;
n->IT->update(q, arr);
}
void update(int p, int q, long long N)
{
update(root, S, E, p, q, N);
}
long long read(node *n, int s, int e, int p, int q, int u, int v)
{
if( !n ) return 0;
if( q < s || e < p) return 0;
else if( p <= s && e <= q){
return n->IT->read(u, v);
}
long long t, fn = 0;
if( e >= s+4){
int mr = (s*3 + e) >> 2;
fn = gcd2(fn, n->d[0]? read(n->d[0], s, mr, p, q, u, v):0);
for(long long i = 1; i < 4; i++){
int ml = (( s*(4-i) + e*i) >> 2) + 1;
int mr = ( s*(3-i) + e*(i+1)) >> 2;
fn = gcd2(fn, n->d[i]? read(n->d[i], ml, mr, p, q, u, v):0);
}
}
else{
for(int j = s, i = 0; j <= e; i++, j++){
t = n->d[i]? read(n->d[i], j, j, p, q, u, v):0;
fn = gcd2(fn, t);
}
}
return fn;
}
long long read(int P,int Q,int U, int V)
{
return read(root, S, E, P, Q, U, V);
}
}*IT;
void init(int R, int C){
IT = new IndexTree(0, R-1, C-1);
}
void update(int R, int C, long long K){
IT->update(R, C, K);
}
long long calculate(int P, int Q, int U, int V){
return IT->read(P, U, Q, V);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1216 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
1216 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1216 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1216 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1216 KB |
Output is correct |
| 4 |
Incorrect |
1376 ms |
8080 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1216 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
1216 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1216 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
1216 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1216 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
1216 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
