Submission #1227828

#TimeUsernameProblemLanguageResultExecution timeMemory
1227828SamurajGame (IOI13_game)C++20
63 / 100
1840 ms279632 KiB
#include "game.h" #include <bits/stdc++.h> using namespace std; #define st first #define nd second #define pb push_back #define rep(i,a,b) for(int i = a; i <= b; i++) #define irep(i,a,b) for(int i = a; i >= b; i--) typedef long long ll; typedef long double ld; //typedef __int128 int128; typedef vector<int> vi; typedef pair<int,int> pi; typedef pair<double,double> pd; typedef pair<ll,ll> pl; 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; } struct n2{ n2* l = nullptr; n2* r = nullptr; ll val = 0; }; struct n1{ n1* l = nullptr; n1* r = nullptr; n2* tree = nullptr; }; const int base = 1<<30; n1* rootx; int lx, rx, ly, ry; ll up_val; ll qy(n2* v, int a, int b){ if(!v) return 0; if(a > ry || b < ly) return 0; if(a >= ly && b <= ry) return v->val; //tu nie musze tworzyc! int mid = (a+b)/2; return gcd2(qy(v->l,a,mid),qy(v->r,mid+1,b)); } ll qx(n1* v, int a, int b){ //cout << "qx, a: " << a << " b: " << b << '\n'; if(!v) return 0; if(a > rx || b < lx) return 0; if(a >= lx && b <= rx) return qy(v->tree,0,base-1); int mid = (a+b)/2; return gcd2(qx(v->l,a,mid),qx(v->r,mid+1,b)); } void uy(n2* v, int a, int b){ //t1 i t2 to pointery do tx->l i tx->r //cout << "uy, a: " << a << " b: " << b << '\n'; if(a > ry || b < ry) return; if(a >= ly && b <= ry){ v->val = up_val; //poczatkowy update return; } //cout << "ostatni case\n"; int mid = (a+b)/2; if(ly <= mid){ if(!v->l) v->l = new n2(); uy(v->l,a,mid); } if(ry >= mid+1){ if(!v->r) v->r = new n2(); uy(v->r,mid+1,b); } //cout << "uy outer loop, a: " << a << " b: " << b << '\n'; //cout << "v->l: " << v->l << " v->r: " << v->r << '\n'; v->val = 0; if(v->l) v->val = gcd2(v->val,v->l->val); //cout << "v->l done\n"; if(v->r) v->val = gcd2(v->val,v->r->val); //cout << "v->r done\n"; } void ux(n1* v, int a, int b){ //cout << "\nux, a: " << a << " b: " << b << '\n'; if(a > rx || b < lx) return; if(a >= lx && b <= rx){ if(!v->tree) v->tree = new n2(); uy(v->tree,0,base-1); return; } //tutaj rownoczesnie tx->tree, tx->l->tree, tx->r->tree int mid = (a+b)/2; if(lx <= mid){ if(!v->l) v->l = new n1(); ux(v->l,a,mid); } if(rx >= mid+1){ if(!v->r) v->r = new n1(); ux(v->r,mid+1,b); } ll val1 = 0; ll val2 = 0; if(v->l) val1 = qy(v->l->tree,0,base-1); if(v->r) val2 = qy(v->r->tree,0,base-1); if(!v->tree) v->tree = new n2(); up_val = gcd2(val1,val2); uy(v->tree,0,base-1); } void init(int R, int C){ rootx = new n1(); } void update(int P, int Q, ll K){ //cout << "\n\nupdate, r: " << P << " c: " << Q << " K: " << K << '\n'; lx = P; rx = P; ly = Q; ry = Q; up_val = K; ux(rootx,0,base-1); } long long calculate(int P, int Q, int U, int V){ //cout << "\n\ncalculate, lx: " << P << " rx: " << U << " ly: " << Q << " ry: " << V << '\n'; lx = P; rx = U; ly = Q; ry = V; return qx(rootx,0,base-1); }
#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...