Submission #119821

#	Time	Username	Problem	Language	Result	Execution time	Memory
119821		nvmdava	Game (IOI13_game)	C++17	10 / 100	321 ms	256000 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct Node{
   int x1, x2, y1, y2;
   long long gcd = 0;
   Node* dx[2] = {NULL};
   Node* dy[2] = {NULL};

   Node(int _x1, int _y1, int _x2, int _y2){
      x1 = _x1;
      y1 = _y1;
      x2 = _x2;
      y2 = _y2;
   }
   void create(){
      if(dx[0] != NULL || dy[0] != NULL) return;
      if(x1 != x2){
         int m = (x1 + x2) >> 1;
         dx[0] = new Node(x1, y1, m, y2);
         dx[1] = new Node(m + 1, y1, x2, y2);
      }
      if(y1 != y2){
         int m = (y1 + y2) >> 1;
         dy[0] = new Node(x1, y1, x2, m);
         dy[1] = new Node(x1, m + 1, x2, y2);
      }
   }

   void update(int x, int y, long long val){
      if(x1 == x2 && y1 == y2){
         gcd = val;
         return;
      }
      create();
      if(x1 != x2){
         int m = (x1 + x2) >> 1;
         dx[x > m] -> update(x, y, val);
         gcd = gcd2(dx[0] -> gcd, dx[1] -> gcd);
      }
      if(y1 != y2){
         int m = (y1 + y2) >> 1;
         dy[y > m] -> update(x, y, val);
         gcd = gcd2(dy[0] -> gcd, dy[1] -> gcd);
      }
   }

   long long query(int qx1, int qy1, int qx2, int qy2){
      if(gcd == 0) return 0;
      if(x1 == x2 && y1 == y2) return gcd;
      if(qx1 == x1 && qx2 == x2 && qy1 == y1 && qy2 == y2) return gcd;
      int mx = (x1 + x2) >> 1;
      int my = (y1 + y2) >> 1;
      if(x1 != x2){
         if(mx >= qx2){
            return dx[0] -> query(qx1, qy1, qx2, qy2);
         } else if(mx < qx1){
            return dx[1] -> query(qx1, qy1, qx2, qy2);
         }
      }
      if(y1 != y2){
         if(my >= qy2){
            return dy[0] -> query(qx1, qy1, qx2, qy2);
         } else if(my < qy1){
            return dy[1] -> query(qx1, qy1, qx2, qy2);
         }
      }
      if(dx[0] != NULL)
         return gcd2(dx[0] -> query(qx1, qy1, mx, qy2), dx[1] -> query(mx + 1, qy1, qx2, qy2));
      return gcd2(dy[0] -> query(qx1, qy1, qx2, my), dy[1] -> query(qx1, my + 1, qx2, qy2));
   }
} *root;


void init(int R, int C) {
   root = new Node(0, 0, R - 1, C - 1);
}

void update(int P, int Q, long long K) {
   root -> update(P, Q, K);
}

long long calculate(int P, int Q, int U, int V){
   return root -> query(P, Q, U, V);
}

Compilation message (stderr)

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 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20