Submission #528934

#TimeUsernameProblemLanguageResultExecution timeMemory
528934AdamGSGame (IOI13_game)C++17
0 / 100
1 ms460 KiB
#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); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...