oj.uz

Submission #119820

# Submission time Handle Problem Language Result Execution time Memory
119820 2019-06-22T12:53:47 Z nvmdava Game (IOI13_game) C++17
0 / 100
 3 ms 384 KB 
#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){
      cerr<<x1<<' '<<y1<<' '<<x2<<' '<<y2<<' ';
      cerr<<qx1<<' '<<qy1<<' '<<qx2<<' '<<qy2<<'\n';
      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

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 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

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