oj.uz

Submission #119824

# Submission time Handle Problem Language Result Execution time Memory
119824 2019-06-22T13:05:27 Z nvmdava Game (IOI13_game) C++17
10 / 100
 342 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 update(int x, int y, long long val){
      if(x1 == x2 && y1 == y2){
         gcd = val;
         return;
      }
      if(x1 != x2){
         int m = (x1 + x2) >> 1;
         if(dx[x > m] == NULL) dx[x > m] = new Node(x > m ? m + 1 : x1, y1, x > m ? x2 : m, y2);
         dx[x > m] -> update(x, y, val);
         gcd = gcd2(dx[0] == NULL ? 0 : dx[0] -> gcd, dx[1] == NULL ? 0 : dx[1] -> gcd);
      }
      if(y1 != y2){
         int m = (y1 + y2) >> 1;
         if(dy[y > m] == NULL) dy[y > m] = new Node(x1, y > m ? m + 1: y1, x2, y > m ? y2 : m);
         dy[y > m] -> update(x, y, val);
         gcd = gcd2(dy[0] == NULL ? 0 : dy[0] -> gcd, dy[1] == NULL ? 0 : 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){
            if(dx[0] == NULL) return 0;
            return dx[0] -> query(qx1, qy1, qx2, qy2);
         } else if(mx < qx1){
            if(dx[1] == NULL) return 0;
            return dx[1] -> query(qx1, qy1, qx2, qy2);
         }
      }
      if(y1 != y2){
         if(my >= qy2){
            if(dy[0] == NULL) return 0;
            return dy[0] -> query(qx1, qy1, qx2, qy2);
         } else if(my < qy1){
            if(dy[1] == NULL) return 0;
            return dy[1] -> query(qx1, qy1, qx2, qy2);
         }
      }
      if(x1 != x2){
         return gcd2(dx[0] == NULL ? 0 : dx[0] -> query(qx1, qy1, mx, qy2), dx[1] == NULL ? 0 : dx[1] -> query(mx + 1, qy1, qx2, qy2));

      }
      return gcd2(dy[0] == NULL ? 0 : dy[0] -> query(qx1, qy1, qx2, my), dy[1] == NULL ? 0 : 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 256 KB Output is correct
2 Correct 80 ms 59768 KB Output is correct
3 Correct 81 ms 59892 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 79 ms 59768 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 1152 KB Output is correct
9 Correct 66 ms 49144 KB Output is correct
10 Correct 27 ms 20088 KB Output is correct
11 Correct 52 ms 25976 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 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Runtime error 342 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 85 ms 59896 KB Output is correct
3 Correct 81 ms 59896 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 81 ms 59896 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 1152 KB Output is correct
9 Correct 66 ms 49084 KB Output is correct
10 Correct 28 ms 20088 KB Output is correct
11 Correct 52 ms 25976 KB Output is correct
12 Runtime error 320 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 384 KB Output is correct
2 Correct 86 ms 59868 KB Output is correct
3 Correct 86 ms 59896 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 82 ms 59896 KB Output is correct
7 Correct 2 ms 356 KB Output is correct
8 Correct 3 ms 1152 KB Output is correct
9 Correct 67 ms 49144 KB Output is correct
10 Correct 27 ms 20088 KB Output is correct
11 Correct 48 ms 25976 KB Output is correct
12 Runtime error 322 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 2 ms 256 KB Output is correct
2 Correct 81 ms 59812 KB Output is correct
3 Correct 82 ms 59896 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 81 ms 59896 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 1152 KB Output is correct
9 Correct 67 ms 49168 KB Output is correct
10 Correct 27 ms 20096 KB Output is correct
11 Correct 48 ms 25996 KB Output is correct
12 Runtime error 332 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -