Submission #1259684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259684		comgaTramAnh	Game (IOI13_game)	C++20	27 / 100	427 ms	125748 KiB

game

#include <bits/stdc++.h>
#include "game.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;
}
long long a[15][100005]; 
long long it[10][10][4 * 100005]; 
void build(int r1, int r2, int index, int L, int R) {
  it[r1][r2][index] = 0;
  if (L == R) {
    return;
  }
  int mid = (L + R) / 2; 
  build(r1, r2, 2 * index, L, mid);
  build(r1, r2, 2 * index + 1, mid + 1, R); 
}
void updateIt(int r1, int r2, int index, int L, int R, int position, long long value) {
  if (position < L || position > R) {
    return; 
  }
  if (L == R) {
    it[r1][r2][index] = value; 
    return; 
  }
  int mid = (L + R) / 2; 
  updateIt(r1, r2, 2 * index, L, mid, position, value); 
  updateIt(r1, r2, 2 * index + 1, mid + 1, R, position, value); 
  it[r1][r2][index] = gcd2(it[r1][r2][2 * index], it[r1][r2][2 * index + 1]); 
}
long long getIt(int r1, int r2, int index, int L, int R, int l, int r) {
  if (l > R || L > r) {
    return 0LL; 
  }             
  if (l <= L && R <= r) {
    return it[r1][r2][index]; 
  }
  int mid = (L + R) / 2; 
  long long leftValue = getIt(r1, r2, 2 * index, L, mid, l, r); 
  long long rightValue = getIt(r1, r2, 2 * index + 1, mid + 1, R, l, r); 
  return gcd2(leftValue, rightValue); 
}
int n, m; 
void init(int R, int C) {
  n = R;
  m = C; 
  for (int i = 0; i < R; i++) {
    for (int j = 0; j < C; j++) {
      a[i][j] = 0; 
    }
  }
  for (int r1 = 0; r1 < R; r1++) {
    for (int r2 = r1; r2 < R; r2++) {
      build(r1, r2, 1, 0, C - 1); 
    }
  }  
}

void update(int P, int Q, long long K) {
  a[P][Q] = K;
  for (int r1 = P; r1 >= 0; r1--) {
    for (int r2 = P; r2 < n; r2++) {
      long long gcd = K; 
      for (int i = P - 1; i >= r1; i--) {
        gcd = gcd2(gcd, a[i][Q]); 
      }
      for (int i = P + 1; i <= r2; i++) {
        gcd = gcd2(gcd, a[i][Q]); 
      }
      updateIt(r1, r2, 1, 0, m - 1, Q, gcd); 
    }
  } 
}

long long calculate(int P, int Q, int U, int V) {
    long long ans = getIt(P, U, 1, 0, m - 1, Q, V); 
    return ans;
}

• Subtask 1: 0 / 10
• Subtask 2: 27 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20