Submission #30151

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
30151	2017-07-22T13:43:00 Z	sampriti	Game (IOI13_game)	C++14	Compilation error	0 ms	0 KB

game

#include "game.h"
#include <cstdio>
#include <algorithm>

using namespace std;

int cnt = 0;
int cnt2 = 0;

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;
}

inline long long gcd(long long X, long long Y, long long Z) {
  return gcd(X, gcd(Y, Z));
}

struct node2 {
  node2 *left, *mid, *right;
  long long val;

  node2(long long _val = 0, node2 *_left = NULL, node2 *_mid = NULL, node2 *_right = NULL) {
    cnt2++;
    val = _val;
    left = _left;
    mid = _mid;
    right = _right;
  }
};

struct node {
  node *left, *mid, *right;
  node2 *val;

  node(node2 *_val = NULL, node *_left = NULL, node *_mid = NULL, node *_right = NULL) {
    cnt++;
    val = _val;
    left = _left;
    mid = _mid;
    right = _right;
  }
};

int R, C;
node* root;

void update2(node2 *& root, int L, int R, int Q, long long K) {
  if(root == NULL) root = new node2();

  if(L == R) {
    root->val = K;
    return;
  }

  int mid1 = L + (R - L + 1)/3;
  int mid2 = R - (R - L + 1)/3;
  if(Q <= mid1) {
    update2(root->left, L, mid1, Q, K);
  }
  else if(Q <= mid2) {
    update2(root->mid, mid1 + 1, mid2, Q, K);
  }
  else {
    update2(root->right, mid2 + 1, R, Q, K);
  }
  root->val = gcd(root->left == NULL ? 0 : root->left->val,
                  root->mid == NULL ? 0 : root->mid->val,
                  root->right == NULL ? 0 : root->right->val);
}

void merge(node2*& root, node2* left, node2* mid, node2* right, int L, int R, int Q) {
  if(root == NULL) root = new node2();

  long long left_val = (left == NULL ? 0 : left->val);
  long long mid_val = (mid == NULL ? 0 : mid->val);
  long long right_val = (right == NULL ? 0 : right->val);

  root->val = gcd(left_val, mid_val, right_val);

  if(L == R) return;

  int mid1 = L + (R - L + 1)/3;
  int mid2 = R - (R - L + 1)/3;
  if (Q <= mid1) {
    merge(root->left,
        (left == NULL ? NULL : left->left),
        (mid == NULL ? NULL : mid->left),
        (right == NULL ? NULL : right->left),
        L, mid1, Q);
  }
  else if(Q <= mid2) {
    merge(root->mid,
        (left == NULL ? NULL : left->mid),
        (mid == NULL ? NULL : mid->mid),
        (right == NULL ? NULL : right->mid),
        mid1 + 1, mid2, Q);
  }
  else {
    merge(root->right,
        (left == NULL ? NULL : left->right),
        (mid == NULL ? NULL : mid->right),
        (right == NULL ? NULL : right->right),
        mid2 + 1, R, Q);
  }
}

void update(node *& root, int L, int R, int P, int Q, long long K) {
  if(root == NULL) root = new node();

  if(L == R) {
    update2(root->val, 0, C - 1, Q, K);
    return;
  }

  int mid1 = L + (R - L + 1)/3;
  int mid2 = R - (R - L + 1)/3;
  if(P <= mid1) {
    update(root->left, L, mid1, P, Q, K);
  }
  else if (P <= mid2) {
    update(root->mid, mid1 + 1, mid2, P, Q, K);
  }
  else {
    update(root->right, mid2 + 1, R, P, Q, K);
  }
  merge(root->val,
      (root->left == NULL ? NULL : root->left->val),
      (root->mid == NULL ? NULL : root->mid->val),
      (root->right == NULL ? NULL : root->right->val),
      0, C - 1, Q);
}

long long query2(node2* root, int L, int R, int C_L, int C_R) {
  if(root == NULL) return 0;
  if(L > R) return 0;
  if(C_L > R || C_R < L) return 0;

  if(C_L <= L && R <= C_R) return root->val;

  int mid1 = L + (R - L + 1)/3;
  int mid2 = R - (R - L + 1)/3;

  long long left = query2(root->left, L, mid1, C_L, C_R);
  long long mid = query2(root->mid, mid1 + 1, mid2, C_L, C_R);
  long long right = query2(root->right, mid2 + 1, R, C_L, C_R);
  return gcd(left, mid, right);
}

long long query(node* root, int L, int R, int R_L, int R_R, int C_L, int C_R) {
  if(root == NULL) return 0;
  if(R_L > R || R_R < L) return 0;

  if(R_L <= L && R <= R_R) return query2(root->val, 0, C - 1, C_L, C_R);

  int mid1 = L + (R - L + 1)/3;
  int mid2 = R - (R - L + 1)/3;

  long long left = query(root->left, L, mid1, R_L, R_R, C_L, C_R);
  long long mid = query(root->mid, mid1 + 1, mid2, R_L, R_R, C_L, C_R);
  long long right = query(root->right, mid2 + 1, R, R_L, R_R, C_L, C_R);
  return gcd(left, mid, right);
}

void init(int _R, int _C) {
  R = _R, C = _C;
  root = NULL;
}

void update(int P, int Q, long long K) {
  update(root, 0, R - 1, P, Q, K);
}

int calculate(int P, int Q, int U, int V) {
  return query(root, 0, R - 1, P, U, Q, V);
}

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 'int calculate(int, int, int, int)':
game.cpp:179:41: error: ambiguating new declaration of 'int calculate(int, int, int, int)'
 int calculate(int P, int Q, int U, int V) {
                                         ^
In file included from game.cpp:1:0:
game.h:10:11: note: old declaration 'long long int calculate(int, int, int, int)'
 long long calculate(int P, int Q, int U, int V);
           ^