Submission #1235501

#TimeUsernameProblemLanguageResultExecution timeMemory
1235501Zbyszek99Game (IOI13_game)C++20
100 / 100
1526 ms83044 KiB
#include "game.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; ll gcd(ll X, ll Y) { if(X > Y) swap(X,Y); while(X > 0) { Y = Y % X; swap(X,Y); } return Y; } struct node { int l = 0; int r = (1 << 30)-1; ll g = 0; node* left; node* right; node() { left = NULL; right = NULL; } ll get_gcd(int l2, int r2) { // cout << l << " " << r << " " << l2 << " " << r2 << " " << g << " gcd\n"; if(l >= l2 && r <= r2) return g; if(r < l2 || l > r2) return 0; return gcd((left != NULL ? left -> get_gcd(l2,r2): 0), (right != NULL ? right -> get_gcd(l2,r2) : 0)); } void change_val(int p, ll x) { // cerr << l << " " << r << " " << p << " " << x << " change_val\n"; if(l == r) { g = x; return; } if(p <= (l+r)/2) { if(left == NULL) { // cerr << " dupa\n"; left = new node; left -> l = p; left -> r = p; left -> g = x; g = gcd(g,x); } else { if(left -> l <= p && left -> r >= p) { left -> change_val(p,x); g = gcd(left -> g, (right != NULL ? right -> g : 0)); return; } // cerr << left->l << " " << left->r << " leftxd\n"; // if(right != NULL) cerr << right->l << " " << right->r << " rightxd\n"; int cur_l = l; int cur_r = r; while(true) { if((cur_l+cur_r)/2 >= p && (cur_l+cur_r)/2 >= left -> l) { cur_r = (cur_l+cur_r)/2; } else if((cur_l+cur_r)/2+1 <= p && (cur_l+cur_r)/2+1 <= left -> l) { cur_l = (cur_l+cur_r)/2+1; } else { node* left2 = new node; left2 -> l = cur_l; left2 -> r = cur_r; node* total_new = new node; total_new -> l = p; total_new -> r = p; total_new -> g = x; if((cur_l+cur_r)/2 >= p) { left2 -> right = left; left2 -> left = total_new; } else { left2 -> left = left; left2 -> right = total_new; } left2 -> g = gcd(left -> g, total_new -> g); left = left2; // cerr << cur_l << " " << cur_r << " " << left -> left -> l << " " << left -> left -> r << " " << left -> right -> l << " " << left -> right -> r << " curlr\n"; g = gcd(left -> g, (right != NULL ? right -> g : 0)); return; } } } } else { if(right == NULL) { right = new node; right -> l = p; right -> r = p; right -> g = x; g = gcd(g,x); } else { if(right -> l <= p && right -> r >= p) { right -> change_val(p,x); g = gcd(right -> g, (left != NULL ? left -> g : 0)); return; } int cur_l = l; int cur_r = r; while(true) { if((cur_l+cur_r)/2 >= p && (cur_l+cur_r)/2 >= right -> l) { cur_r = (cur_l+cur_r)/2; } else if((cur_l+cur_r)/2+1 <= p && (cur_l+cur_r)/2+1 <= right -> l) { cur_l = (cur_l+cur_r)/2+1; } else { node* right2 = new node; right2 -> l = cur_l; right2 -> r = cur_r; node* total_new = new node; total_new -> l = p; total_new -> r = p; total_new -> g = x; if((cur_l+cur_r)/2 >= p) { right2 -> right = right; right2 -> left = total_new; } else { right2 -> left = right; right2 -> right = total_new; } right2 -> g = gcd(right -> g, total_new -> g); right = right2; // cerr << cur_l << " " << cur_r << " " << right -> left -> l << " " << right -> left -> r << " " << right -> right -> l << " " << right -> right -> r << " curlr\n"; g = gcd(right -> g, (left != NULL ? left -> g : 0)); return; } } } } } }; struct node2 { int l = 0; int r = (1 << 30)-1; node2* left; node2* right; node* tr; node2() { left = NULL; right = NULL; tr = new node; } ll upd(int p1, int p2, ll x) { if(l == r) { tr -> change_val(p2,x); return x; } if(p1 <= (l+r)/2) { if(left == NULL) { left = new node2; left -> l = l; left -> r = (l+r)/2; } ll g = gcd(left -> upd(p1,p2,x),(right != NULL ? right -> tr -> get_gcd(p2,p2) : 0)); tr -> change_val(p2,g); // cerr << l << " " << r << " " << g << " " << p1 << " " << p2 << " " << x << " upd\n"; return g; } else { if(right == NULL) { right = new node2; right -> l = (l+r)/2+1; right -> r = r; } ll g = gcd(right -> upd(p1,p2,x), (left != NULL ? left -> tr -> get_gcd(p2,p2) : 0)); tr -> change_val(p2,g); // cerr << l << " " << r << " " << g << " " << p1 << " " << p2 << " " << x << " upd\n"; return g; } } ll get_gcd(int l1, int r1, int l2, int r2) { if(l >= l1 && r <= r1) { // cerr << l << " " << r << " " << val << l2 << " " << r2 << " from\n\n\n"; return tr -> get_gcd(l2,r2); } if(r < l1 || l > r1) return 0; return gcd((left != NULL ? left -> get_gcd(l1,r1,l2,r2) : 0),(right != NULL ? right -> get_gcd(l1,r1,l2,r2) : 0)); } }; node2 root; void init(int R, int C) { } void update(int P, int Q, ll K) { root.upd(P,Q,K); } ll calculate(int P, int Q, int U, int V) { return root.get_gcd(P,U,Q,V); }
#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...