oj.uz

Submission #120294

# Submission time Handle Problem Language Result Execution time Memory
120294 2019-06-24T06:54:58 Z nvmdava Game (IOI13_game) C++11
63 / 100
 2790 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 256 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 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 256 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 Correct 2 ms 384 KB Output is correct

Subtask #2
27.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 3 ms 384 KB Output is correct
4 Correct 637 ms 17016 KB Output is correct
5 Correct 391 ms 16892 KB Output is correct
6 Correct 653 ms 14536 KB Output is correct
7 Correct 784 ms 14308 KB Output is correct
8 Correct 494 ms 11008 KB Output is correct
9 Correct 810 ms 14392 KB Output is correct
10 Correct 694 ms 13928 KB Output is correct
11 Correct 2 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 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 356 KB Output is correct
12 Correct 971 ms 19852 KB Output is correct
13 Correct 2243 ms 10172 KB Output is correct
14 Correct 297 ms 5856 KB Output is correct
15 Correct 2622 ms 13248 KB Output is correct
16 Correct 305 ms 22572 KB Output is correct
17 Correct 1379 ms 16632 KB Output is correct
18 Correct 2304 ms 23936 KB Output is correct
19 Correct 2161 ms 24128 KB Output is correct
20 Correct 2100 ms 23688 KB Output is correct
21 Correct 2 ms 256 KB Output is correct

Subtask #4
0 / 17.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 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 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 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 658 ms 17080 KB Output is correct
13 Correct 424 ms 16888 KB Output is correct
14 Correct 737 ms 14560 KB Output is correct
15 Correct 851 ms 14456 KB Output is correct
16 Correct 573 ms 10996 KB Output is correct
17 Correct 792 ms 14456 KB Output is correct
18 Correct 834 ms 14004 KB Output is correct
19 Correct 1008 ms 19928 KB Output is correct
20 Correct 2326 ms 10196 KB Output is correct
21 Correct 303 ms 5624 KB Output is correct
22 Correct 2615 ms 13308 KB Output is correct
23 Correct 282 ms 22396 KB Output is correct
24 Correct 1302 ms 16588 KB Output is correct
25 Correct 2564 ms 23988 KB Output is correct
26 Correct 2089 ms 24028 KB Output is correct
27 Correct 1907 ms 23560 KB Output is correct
28 Correct 1231 ms 256000 KB Output is correct
29 Runtime error 2237 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 2 ms 384 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 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 718 ms 17256 KB Output is correct
13 Correct 410 ms 16912 KB Output is correct
14 Correct 706 ms 14584 KB Output is correct
15 Correct 768 ms 14296 KB Output is correct
16 Correct 490 ms 11008 KB Output is correct
17 Correct 828 ms 14536 KB Output is correct
18 Correct 670 ms 13944 KB Output is correct
19 Correct 1004 ms 19768 KB Output is correct
20 Correct 2523 ms 10372 KB Output is correct
21 Correct 312 ms 5752 KB Output is correct
22 Correct 2790 ms 13124 KB Output is correct
23 Correct 293 ms 22492 KB Output is correct
24 Correct 1285 ms 16372 KB Output is correct
25 Correct 2343 ms 24104 KB Output is correct
26 Correct 2126 ms 24148 KB Output is correct
27 Correct 1712 ms 23568 KB Output is correct
28 Correct 1213 ms 256000 KB Output is correct
29 Runtime error 2145 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -