oj.uz

Submission #120074

# Submission time Handle Problem Language Result Execution time Memory
120074 2019-06-23T07:55:28 Z nvmdava Game (IOI13_game) C++17
63 / 100
 2668 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;
   long long query(int l, int r){
      if(l > V || r < Q) return 0;
      if(l >= Q && r <= V) return val;
      int m = (l + r) >> 1;
      return gcd2(ll == NULL ? 0LL : ll -> query(l, m), rr == NULL ? 0LL : rr -> query(m + 1, r));
   }
   void update(int l, int r, long long K){
      if(l == r){
         val = K;
         return;
      }
      int m = (l + r) >> 1;
      if(m < Q){
         if(rr == NULL) rr = new Y();
         rr -> update(m + 1, r, K);
      } else {
         if(ll == NULL) ll = new Y();
         ll -> update(l, m, K);
      }
      val = gcd2(ll == NULL ? 0LL : ll -> val, rr == NULL ? 0LL : rr -> val);
   }
};

struct X{
   X *ll = NULL, *rr = NULL;
   Y *tree = new Y();
   long long query(int l, int r){
      if(l > U || r < P) return 0;
      if(l >= P && r <= U) return tree == NULL ? 0LL : tree -> query(0, c);
      int m = (l + r) >> 1;
      return gcd2(ll == NULL ? 0LL : ll -> query(l, m), rr == NULL ? 0LL : rr -> query(m + 1, r));
   }
   void update(int l, int r, long long K){
      if(l == r){
         tree -> update(0, c, K);
         return;
      }
      int m = (l + r) >> 1;
      if(m < P){
         if(rr == NULL) rr = new X();
         rr -> update(m + 1, r, K);
      } else {
         if(ll == NULL) ll = new X();
         ll -> update(l, m, K);
      }
      tree -> update(0, c, gcd2(ll == NULL ? 0 : ll -> tree -> query(0, c), rr == NULL ? 0LL : rr -> tree -> query(0, c)));
   }
} *root = new X();

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;
   root -> update(0, r, K);
}

long long calculate(int P, int Q, int U, int V){
   ::P = P; ::Q = Q; ::U = U; ::V = V;
   return root -> query(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 3 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 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 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 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 854 ms 13680 KB Output is correct
5 Correct 415 ms 13816 KB Output is correct
6 Correct 717 ms 10880 KB Output is correct
7 Correct 805 ms 10744 KB Output is correct
8 Correct 498 ms 7704 KB Output is correct
9 Correct 825 ms 10872 KB Output is correct
10 Correct 740 ms 10488 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 3 ms 540 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 356 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 384 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 3 ms 384 KB Output is correct
12 Correct 970 ms 16760 KB Output is correct
13 Correct 2226 ms 7292 KB Output is correct
14 Correct 293 ms 2044 KB Output is correct
15 Correct 2668 ms 9784 KB Output is correct
16 Correct 300 ms 19320 KB Output is correct
17 Correct 1349 ms 12664 KB Output is correct
18 Correct 2371 ms 19768 KB Output is correct
19 Correct 1990 ms 19740 KB Output is correct
20 Correct 2007 ms 18960 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 256 KB Output is correct
2 Correct 2 ms 384 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 384 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 356 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 694 ms 13384 KB Output is correct
13 Correct 395 ms 13688 KB Output is correct
14 Correct 688 ms 10884 KB Output is correct
15 Correct 745 ms 10332 KB Output is correct
16 Correct 466 ms 7492 KB Output is correct
17 Correct 751 ms 10716 KB Output is correct
18 Correct 652 ms 10004 KB Output is correct
19 Correct 1046 ms 16548 KB Output is correct
20 Correct 2314 ms 7168 KB Output is correct
21 Correct 335 ms 1784 KB Output is correct
22 Correct 2631 ms 9720 KB Output is correct
23 Correct 271 ms 19056 KB Output is correct
24 Correct 1342 ms 12408 KB Output is correct
25 Correct 2461 ms 19372 KB Output is correct
26 Correct 1870 ms 19684 KB Output is correct
27 Correct 1721 ms 19064 KB Output is correct
28 Correct 1160 ms 256000 KB Output is correct
29 Runtime error 2129 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 5 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 384 KB Output is correct
6 Correct 3 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 Correct 626 ms 13432 KB Output is correct
13 Correct 415 ms 13764 KB Output is correct
14 Correct 708 ms 10688 KB Output is correct
15 Correct 802 ms 10488 KB Output is correct
16 Correct 466 ms 7672 KB Output is correct
17 Correct 736 ms 10488 KB Output is correct
18 Correct 631 ms 10104 KB Output is correct
19 Correct 944 ms 16880 KB Output is correct
20 Correct 2184 ms 7032 KB Output is correct
21 Correct 291 ms 1820 KB Output is correct
22 Correct 2522 ms 9604 KB Output is correct
23 Correct 269 ms 19064 KB Output is correct
24 Correct 1294 ms 12320 KB Output is correct
25 Correct 2377 ms 19476 KB Output is correct
26 Correct 1881 ms 19652 KB Output is correct
27 Correct 1747 ms 18808 KB Output is correct
28 Correct 1146 ms 256000 KB Output is correct
29 Runtime error 2080 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -