Submission #528934

#	Time	Username	Problem	Language	Result	Execution time	Memory
528934		AdamGS	Game (IOI13_game)	C++17	0 / 100	1 ms	460 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct NodeC {
  ll val;
  NodeC *l, *r;
  NodeC() : val(0), l(nullptr), r(nullptr) {}
};
struct NodeR {
  NodeC *root;
  NodeR *l, *r;
  NodeR() : root(nullptr), l(nullptr), r(nullptr) {}
};
int N, M;
NodeR *root;
void updC(NodeC *v, int l, int r, int a, ll x) {
  if(a<l || a>r) return;
  if(l==r) {
    v->val=x;
    return;
  }
  if(v->l==nullptr) v->l=new NodeC();
  if(v->r==nullptr) v->r=new NodeC();
  int mid=(l+r)/2;
  updC(v->l, l, mid, a, x);
  updC(v->r, mid+1, r, a, x);
  v->val=__gcd((v->l)->val, (v->r)->val);
}
void updR(NodeR *v, int l, int r, int a, int b, ll x) {
  if(a<l || a>r) return;
  if(v->root==nullptr) v->root=new NodeC();
  updC(v->root, 0, M-1, b, x);
  if(l==r) return;
  if(v->l==nullptr) v->l=new NodeR();
  if(v->r==nullptr) v->r=new NodeR();
  int mid=(l+r)/2;
  updR(v->l, l, mid, a, b, x);
  updR(v->r, mid+1, r, a, b, x);
}
ll cntC(NodeC *v, int l, int r, int a, int b) {
  if(b<l || a>r) return 0;
  if(a<=l && r<=b) return v->val;
  int mid=(l+r)/2;
  ll ans=0;
  if(v->l!=nullptr) ans=__gcd(ans, cntC(v->l, l, mid, a, b));
  if(v->r!=nullptr) ans=__gcd(ans, cntC(v->r, mid+1, r, a, b));
  return ans;
}
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;
  }
  int mid=(l+r)/2;
  ll ans=0;
  if(v->l!=nullptr) ans=__gcd(ans, cntR(v->l, l, mid, ar, br, ac, bc));
  if(v->r!=nullptr) ans=__gcd(ans, cntR(v->r, mid+1, r, ar, br, ac, bc));
  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: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20