Submission #120058

#	Time	Username	Problem	Language	Result	Execution time	Memory
120058		nvmdava	Game (IOI13_game)	C++17	63 / 100	11036 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;
}
#define N 1073741824
map<int, map<int, long long> > tree;

void init(int R, int C){};

long long get(map<int, long long>& pnt, int key){
   auto it = pnt.find(key);
   if(it == pnt.end()) return 0;
   return it -> second;
}

void update(int P, int Q, long long K) {
   int idx = P + N;
   int idy = Q + N;
   int t = idy >> 1;
   auto& pntr = tree[idx];
   pntr[idy] = K;
   while(t){
      pntr[t] = gcd2(get(pntr, t << 1), get(pntr, t << 1 | 1));
      t >>= 1;
   }

   idx >>= 1;
   while(idx){
      t = idy >> 1;
      auto& pntrr = tree[idx];
      pntrr[idy] = gcd2(get(tree[idx << 1], idy), get(tree[idx << 1 | 1], idy));
      while(t){
         pntrr[t] = gcd2(get(pntrr, t << 1), get(pntrr, t << 1 | 1));
         t >>= 1;
      }
      idx >>= 1;
   }
}

long long solve(map<int, long long>& pntr, int id, int l, int r, int L, int R){
   if(l > R || r < L) return 0;
   if(l >= L && r <= R){
      return get(pntr, id);
   }
   int m =(l + r) >> 1;
   return gcd2(solve(pntr, id << 1, l, m, L, R), solve(pntr, id << 1 | 1, m + 1, r, L, R));
}

long long solve(int id, int l, int r, int L, int R, int U, int V){
   if(l > R || r < L) return 0;
   if(l >= L && r <= R){
      return solve(tree[id], 1, 1, N, U, V);
   }
   int m = (l + r) >> 1;
   return gcd2(solve(id << 1, l, m, L, R, U, V), solve(id << 1 | 1, m + 1, r, L, R, U, V));
}

long long calculate(int P, int Q, int U, int V){
   return solve(1, 1, N, 1 + P, 1 + U, 1 + Q, 1 + V);
}

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