oj.uz

Submission #119798

# Submission time Handle Problem Language Result Execution time Memory
119798 2019-06-22T11:25:59 Z nvmdava Game (IOI13_game) C++17
10 / 100
 13000 ms 12340 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 *t[2][2] = {{NULL}};

   Node(int _x1, int _y1, int _x2, int _y2){
      x1 = _x1;
      y1 = _y1;
      x2 = _x2;
      y2 = _y2;
   }

   void create(){
      if(t[0][0] != NULL) return;
      int mx = (x1 + x2) >> 1;
      int my = (y1 + y2) >> 1;
      t[0][0] = new Node(x1, y1, mx, my);
      t[1][0] = new Node(mx + 1, y1, x2, my);
      t[0][1] = new Node(x1, my + 1, mx, y2);
      t[1][1] = new Node(mx + 1, my + 1, x2, y2);
   }

   void update(int x, int y, long long val){
      if(x1 == x2 && y1 == y2){
         gcd = val;
         return;
      }
      create();
      int mx = (x1 + x2) >> 1;
      int my = (y1 + y2) >> 1;
      if(x <= mx && y <= my)
         t[0][0] -> update(x, y, val);
      if(x > mx && y <= my)
         t[1][0] -> update(x, y, val);
      if(x <= mx && y > my)
         t[0][1] -> update(x, y, val);
      if(x > mx && y > my)
         t[1][1] -> update(x, y, val);

      gcd = gcd2(gcd2(t[0][0] -> gcd, t[1][1] -> gcd), gcd2(t[0][1] -> gcd, t[1][0] -> gcd));
   }

   long long query(int qx1, int qy1, int qx2, int qy2){
      if(qx1 > x2 || qy1 > y2 || qy2 < y1 || qx2 < x1) return 0;
      if(gcd == 0) return 0;
      if(qx1 <= x1 && qx2 >= x2 && qy1 <= y1 && qy2 >= y2) return gcd;
      return gcd2(gcd2(t[0][0] -> query(qx1, qy1, qx2, qy2), t[0][1] -> query(qx1, qy1, qx2, qy2)), gcd2(t[1][0] -> query(qx1, qy1, qx2, qy2), t[1][1] -> query(qx1, qy1, qx2, qy2)));
   }
} *root;


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

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 2 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 356 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 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 256 KB Output is correct
4 Incorrect 415 ms 4976 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 9238 ms 12340 KB Output is correct
13 Execution timed out 13015 ms 3976 KB Time limit exceeded
14 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 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Incorrect 414 ms 4940 KB Output isn't correct
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 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Incorrect 425 ms 4476 KB Output isn't correct
13 Halted 0 ms 0 KB -