Submission #1136626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136626		mychecksedad	Game (IOI13_game)	C++20	0 / 100	125 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 = 8005, M = 1e5+10, 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;
}

vector<ll> T[N][N];
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;
  // }
}
ll get(vector<ll> &v){
  if(v.empty()) return 0ll;
  return v[0];
}

void upd(vector<ll> &v, ll val){
  if(v.empty()) v.pb(val);
  else v[0] = val;
}

ll gcd3(vector<ll> &x, vector<ll> &y){
  return gcd2(get(x), get(y));
}

void updY(int l, int r, int p, int lx, int rx, int k, int kx, ll val){
  if(l == r){
    if(lx == rx){
      upd(T[kx][k], val);
    }else{
      upd(T[kx][k], gcd3(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);
    upd(T[kx][k], gcd3(T[kx][k<<1], T[kx][k<<1|1]));
  }
}

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