Submission #916424

#TimeUsernameProblemLanguageResultExecution timeMemory
916424AverageAmogusEnjoyerGame (IOI13_game)C++17
0 / 100
19 ms1588 KiB
#include "game.h" #include <bits/stdc++.h> using namespace std; using ll = long long; template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; } template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; } const int nax = 1e9; struct node_st2 { ll ans=0; node_st2 *left_child=nullptr,*right_child=nullptr; int l,r; node_st2(int _l,int _r) : l(_l) , r(_r) {} void extend() { if (!left_child && l != r) { int mid = (l+r)/2; left_child = new node_st2(l,mid); right_child = new node_st2(mid+1,r); } } void upd(int p,ll x) { extend(); ans=gcd(gcd(get_gcd(l,p-1),get_gcd(p+1,r)),x); if (left_child) { if (p <= left_child->r) { left_child->upd(p,x); } else { right_child->upd(p,x); } } } ll get_gcd(int tl,int tr) { if (tl > tr) { return 0LL; } if (tl <= l && r <= tr) { return ans; } if (tr < l || tl > r) { return 0LL; } extend(); return gcd(left_child->get_gcd(tl,tr),right_child->get_gcd(tl,tr)); } }; struct node_st1 { node_st2 *root; node_st1 *left_child=nullptr,*right_child=nullptr; int l,r; node_st1(int _l,int _r) { l = _l; r = _r; root = new node_st2(0,nax); } void extend() { if (!left_child && l != r) { int mid = (l+r)/2; left_child = new node_st1(l,mid); right_child = new node_st1(mid+1,r); } } void upd(int x,int y,ll nw) { extend(); root->upd(y,nw); if (left_child) { if (x <= left_child->r) { left_child->upd(x,y,nw); } else { right_child->upd(x,y,nw); } } } ll get_gcd(int x1,int y1,int x2,int y2) { if (x1 <= l && r <= x2) { return root->get_gcd(y1,y2); } if (x2 < l || x1 > r) { return 0LL; } extend(); return gcd(left_child->get_gcd(x1,y1,x2,y2),right_child->get_gcd(x1,y1,x2,y2)); } }; node_st1 *root = new node_st1(0,nax); void init(int r,int c) { // AMOGUS } void update(int x,int y,ll nw) { root->upd(x,y,nw); } ll calculate(int x1,int y1,int x2,int y2) { return root->get_gcd(x1,y1,x2,y2); }
#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...