oj.uz

Submission #120076

# Submission time Handle Problem Language Result Execution time Memory
120076 2019-06-23T08:09:17 Z nvmdava Game (IOI13_game) C++17
63 / 100
 2583 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;
}
int r, c;
int P, U, Q, V;
struct Y{
   Y *ll = NULL, *rr = NULL;
   long long val = 0;
};
void updateY(Y* y, int l, int r, long long K){
   if(l == r){
      y -> val = K;
      return;
   }
   int m = (l + r) >> 1;
   if(m < Q){
      if(y -> rr == NULL) y -> rr = new Y();
      updateY(y -> rr, m + 1, r, K);
   } else {
      if(y -> ll == NULL) y -> ll = new Y();
      updateY(y -> ll, l, m, K);
   }
   y -> val = gcd2(y -> ll == NULL ? 0LL : y -> ll -> val, y -> rr == NULL ? 0LL : y -> rr -> val);
}

long long queryY(Y* y, int l, int r){
   if(l > V || r < Q) return 0;
   if(l >= Q && r <= V) return y -> val;
   int m = (l + r) >> 1;
   return gcd2(y -> ll == NULL ? 0LL : queryY(y -> ll, l, m), y -> rr == NULL ? 0LL : queryY(y -> rr, m + 1, r));
}
struct X{
   X *ll = NULL, *rr = NULL;
   Y *tree = new Y();
} *root = new X();

long long queryX(X *x, int l, int r){
   if(l > U || r < P) return 0;
   if(l >= P && r <= U) return x -> tree == NULL ? 0LL : queryY(x -> tree, 0, c);
   int m = (l + r) >> 1;
   return gcd2(x -> ll == NULL ? 0LL : queryX(x -> ll, l, m), x -> rr == NULL ? 0LL : queryX(x -> rr, m + 1, r));
}
void updateX(X *x, int l, int r, long long K){
   if(l == r){
      updateY(x -> tree, 0, c, K);
      return;
   }
   int m = (l + r) >> 1;
   if(m < P){
      if(x -> rr == NULL) x -> rr = new X();
      updateX(x -> rr, m + 1, r, K);
   } else {
      if(x -> ll == NULL) x -> ll = new X();
      updateX(x -> ll, l, m, K);
   }
   updateY(x -> tree, 0, c, gcd2(x -> ll == NULL ? 0 : queryY(x -> ll -> tree, 0, c), x -> rr == NULL ? 0LL : queryY(x -> rr -> tree, 0, c)));
}
void init(int R, int C){
   r = R - 1; c = C - 1;
};

void update(int P, int Q, long long K) {
   ::P = P; ::Q = Q; ::U = P; ::V = Q;
   updateX(root, 0, r, K);
}

long long calculate(int P, int Q, int U, int V){
   ::P = P; ::Q = Q; ::U = U; ::V = V;
   return queryX(root, 0, r);
}

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 3 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 384 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 Correct 2 ms 384 KB Output is correct

Subtask #2
27.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 256 KB Output is correct
4 Correct 637 ms 12700 KB Output is correct
5 Correct 403 ms 12996 KB Output is correct
6 Correct 691 ms 9976 KB Output is correct
7 Correct 825 ms 9720 KB Output is correct
8 Correct 502 ms 6736 KB Output is correct
9 Correct 764 ms 9848 KB Output is correct
10 Correct 632 ms 9464 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 512 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 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 968 ms 15816 KB Output is correct
13 Correct 2219 ms 6384 KB Output is correct
14 Correct 299 ms 1016 KB Output is correct
15 Correct 2583 ms 8924 KB Output is correct
16 Correct 275 ms 18296 KB Output is correct
17 Correct 1223 ms 11768 KB Output is correct
18 Correct 2524 ms 18772 KB Output is correct
19 Correct 1902 ms 18912 KB Output is correct
20 Correct 1754 ms 18296 KB Output is correct
21 Correct 2 ms 384 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 512 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 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 428 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 356 KB Output is correct
12 Correct 630 ms 12664 KB Output is correct
13 Correct 392 ms 13124 KB Output is correct
14 Correct 684 ms 10064 KB Output is correct
15 Correct 772 ms 9976 KB Output is correct
16 Correct 454 ms 7024 KB Output is correct
17 Correct 726 ms 9976 KB Output is correct
18 Correct 642 ms 9744 KB Output is correct
19 Correct 965 ms 16224 KB Output is correct
20 Correct 2225 ms 6676 KB Output is correct
21 Correct 298 ms 1272 KB Output is correct
22 Correct 2565 ms 9096 KB Output is correct
23 Correct 282 ms 18552 KB Output is correct
24 Correct 1219 ms 11896 KB Output is correct
25 Correct 2531 ms 19032 KB Output is correct
26 Correct 2070 ms 19104 KB Output is correct
27 Correct 1872 ms 18528 KB Output is correct
28 Correct 1296 ms 256000 KB Output is correct
29 Runtime error 2184 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 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 3 ms 512 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 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 652 ms 12908 KB Output is correct
13 Correct 397 ms 13116 KB Output is correct
14 Correct 718 ms 10232 KB Output is correct
15 Correct 781 ms 10124 KB Output is correct
16 Correct 453 ms 6904 KB Output is correct
17 Correct 781 ms 10232 KB Output is correct
18 Correct 705 ms 9636 KB Output is correct
19 Correct 954 ms 16120 KB Output is correct
20 Correct 2253 ms 6660 KB Output is correct
21 Correct 300 ms 1272 KB Output is correct
22 Correct 2575 ms 9208 KB Output is correct
23 Correct 280 ms 18552 KB Output is correct
24 Correct 1417 ms 11840 KB Output is correct
25 Correct 2319 ms 18936 KB Output is correct
26 Correct 2139 ms 19192 KB Output is correct
27 Correct 1852 ms 18552 KB Output is correct
28 Correct 1190 ms 256000 KB Output is correct
29 Runtime error 2168 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -