oj.uz

Submission #119821

# Submission time Handle Problem Language Result Execution time Memory
119821 2019-06-22T12:54:51 Z nvmdava Game (IOI13_game) C++17
10 / 100
 321 ms 256000 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){
      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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 144 ms 116344 KB Output is correct
3 Correct 146 ms 116344 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 128 KB Output is correct
6 Correct 146 ms 116516 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 4 ms 1920 KB Output is correct
9 Correct 118 ms 95736 KB Output is correct
10 Correct 50 ms 39672 KB Output is correct
11 Correct 64 ms 40056 KB Output is correct
12 Correct 2 ms 256 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Runtime error 306 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 145 ms 116472 KB Output is correct
3 Correct 147 ms 116332 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 144 ms 116292 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 4 ms 1920 KB Output is correct
9 Correct 123 ms 95864 KB Output is correct
10 Correct 51 ms 39672 KB Output is correct
11 Correct 64 ms 40128 KB Output is correct
12 Runtime error 296 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 149 ms 116336 KB Output is correct
3 Correct 151 ms 116344 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 144 ms 116344 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 4 ms 1920 KB Output is correct
9 Correct 123 ms 95740 KB Output is correct
10 Correct 52 ms 39672 KB Output is correct
11 Correct 67 ms 40056 KB Output is correct
12 Runtime error 313 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 152 ms 116344 KB Output is correct
3 Correct 154 ms 116384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 151 ms 116420 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 4 ms 1920 KB Output is correct
9 Correct 123 ms 95704 KB Output is correct
10 Correct 127 ms 39672 KB Output is correct
11 Correct 68 ms 40168 KB Output is correct
12 Runtime error 321 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -