Submission #120074

#	Time	Username	Problem	Language	Result	Execution time	Memory
120074		nvmdava	Game (IOI13_game)	C++17	63 / 100	2668 ms	256000 KiB

game

#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 (stderr)

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20