제출 #1227808

#제출 시각아이디문제언어결과실행 시간메모리
1227808Samuraj게임 (IOI13_game)C++20
63 / 100
2032 ms321536 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 node{ node* l = nullptr; node* r = nullptr; node* tree = nullptr; ll val = 0; }; const int base = 1<<30; node* rootx; int lx, rx, ly, ry; ll up_val; ll qy(node* 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(node* 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(node* 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"; if(!v->l) v->l = new node(); if(!v->r) v->r = new node(); int mid = (a+b)/2; //cout << "stworzone new nodes\n"; uy(v->l,a,mid); uy(v->r,mid+1,b); //teraz update naszego v->val = gcd2(v->l->val,v->r->val); } void ux(node* 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 node(); uy(v->tree,0,base-1); return; } //tutaj rownoczesnie tx->tree, tx->l->tree, tx->r->tree if(!v->l) v->l = new node(); if(!v->r) v->r = new node(); int mid = (a+b)/2; ux(v->l,a,mid); ux(v->r,mid+1,b); if(!v->tree) v->tree = new node(); ll val1 = qy(v->l->tree,0,base-1); ll val2 = qy(v->r->tree,0,base-1); up_val = gcd2(val1,val2); uy(v->tree,0,base-1); } void init(int R, int C){ rootx = new node(); } 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...