Submission #1136634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136634		mychecksedad	Game (IOI13_game)	C++20	10 / 100	933 ms	321536 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 10000, M = 1e5+10, K = 52, MX = 30;

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;
}

map<int, ll> T[N];
// ll T[8005][8005];
int n, m;
void init(int R, int C) {
  n = R;
  m = C;
  for(int i = 0; i <= 4*n; ++i){
    for(int j = 0; j <= 4*m; ++j) T[i][j] = 0;
  }
}

void updY(int l, int r, int p, int lx, int rx, int k, int kx, ll val){
  if(l == r){
    if(lx == rx){
      T[kx][k] = val;
    }else{
      T[kx][k] = gcd2(T[kx<<1][k], T[kx<<1|1][k]);
    }
  }else{
    int m = l+r>>1;
    if(p <= m) updY(l, m, p, lx, rx, k<<1, kx, val);
    else updY(m+1, r, p, lx, rx, k<<1|1, kx, val);

    if(lx == rx){
      T[kx][k] = gcd2(T[kx][k<<1], T[kx][k<<1|1]);
    }else{
      T[kx][k] = gcd2(T[kx<<1][k], T[kx<<1|1][k]);
    }
  }
}

void updX(int l, int r, int p, int k, int y, ll val){
  if(l != r){
    int m = l+r>>1;
    if(p <= m) updX(l, m, p, k<<1, y, val);
    else updX(m+1, r, p, k<<1|1, y, val);
  }
  updY(1, m, y, l, r, 1, k, val);
}


void update(int P, int Q, long long K) {
  ++P, ++Q;
  updX(1, n, P, 1, Q, K);
}

ll getY(int l, int r, int ly, int ry, int k, int kx){
  if(ly > r || l > ry) return 0ll;
  if(ly <= l && r <= ry){
    if(T[kx].find(k) == T[kx].end()) return 0ll;
    return T[kx][k];
  }
  int m = l+r>>1;
  return gcd2(getY(l, m, ly, ry, k<<1, kx), getY(m + 1, r, ly, ry, k<<1|1, kx));
}

ll getX(int l, int r, int lx, int rx, int k, int ly, int ry){
  if(lx > r || l > rx) return 0ll;
  if(lx <= l && r <= rx){
    return getY(1, m, ly, ry, 1, k);
  }
  int m = l+r>>1;
  return gcd2(getX(l, m, lx, rx, k<<1, ly, ry), getX(m+1, r, lx, rx, k<<1|1, ly, ry));
}

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

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