Submission #529003

#	Time	Username	Problem	Language	Result	Execution time	Memory
529003		AdamGS	Game (IOI13_game)	C++17	100 / 100	9495 ms	203296 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int base=10;
struct NodeC {
  ll val=0;
  NodeC *children[base]={};
};
struct NodeR {
  NodeC *root=nullptr;
  NodeR *children[base]={};
};
int N, M;
NodeR *root;
void updC(NodeC *v, int l, int r, int a, ll x) {
  if(l==r) {
    v->val=x;
    return;
  }
  int p=(r-l)/base+1, akt=l;
  v->val=0;
  for(int i=0; akt<=r; ++i) {
    if(akt<=a && a<=min(akt+p-1, r)) {
      if(v->children[i]==nullptr) v->children[i]=new NodeC();
      updC(v->children[i], akt, min(akt+p-1, r), a, x);
    }
    akt+=p;
    if(v->children[i]!=nullptr) v->val=gcd(v->val, (v->children[i])->val);
  }
}
ll cntC(NodeC *v, int l, int r, int a, int b) {
  if(v==nullptr || b<l || a>r) return 0;
  if(a<=l && r<=b) return v->val;
  ll ans=0;
  int p=(r-l)/base+1, akt=l;
  for(int i=0; akt<=r; ++i) {
    if(v->children[i]!=nullptr) {
      ans=gcd(ans, cntC(v->children[i], akt, min(akt+p-1, r), a, b));
    }
    akt+=p;
  }
  return ans;
}
void updR(NodeR *v, int l, int r, int a, int b, ll x) {
  if(v->root==nullptr) v->root=new NodeC();
  if(l!=r) {
    int p=(r-l)/base+1, akt=l;
    for(int i=0; akt<=r; ++i) {
      if(akt<=a && a<=min(akt+p-1, r)) {
        if(v->children[i]==nullptr) v->children[i]=new NodeR();
        updR(v->children[i], akt, min(akt+p-1, r), a, b, x);
      }
      akt+=p;
    }
    akt=l;
    ll y=0;
    for(int i=0; akt<=r; ++i) {
      if(v->children[i]!=nullptr) {
        y=gcd(y, cntC((v->children[i])->root, 0, M-1, b, b));
      }
      akt+=p;
    }
    x=y;
  }
  updC(v->root, 0, M-1, b, x);
}
ll cntR(NodeR *v, int l, int r, int ar, int br, int ac, int bc) {
  if(br<l || ar>r) return 0;
  if(ar<=l && r<=br) {
    if(v->root!=nullptr) return cntC(v->root, 0, M-1, ac, bc);
    return 0;
  }
  ll ans=0;
  int p=(r-l)/base+1, akt=l;
  for(int i=0; akt<=r; ++i) {
    if(v->children[i]!=nullptr) {
      ans=gcd(ans, cntR(v->children[i], akt, min(akt+p-1, r), ar, br, ac, bc));
    }
    akt+=p;
  }
  return ans;
}
void init(int R, int C) {
  N=R;
  M=C;
  root=new NodeR();
}
void update(int a, int b, ll x) {
  updR(root, 0, N-1, a, b, x);
}
ll calculate(int ar, int ac, int br, int bc) {
  return cntR(root, 0, N-1, ar, br, ac, bc);
}

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