Submission #901590

#TimeUsernameProblemLanguageResultExecution timeMemory
901590trMatherzGame (IOI13_game)C++17
0 / 100
0 ms348 KiB
//#include <iostream> //cin, cout #include "game.h" /* #include <fstream> std::ifstream cin ("ex.in"); std::ofstream cout ("ex.out"); */ // includes #include <cmath> #include <set> #include <map> #include <queue> #include <string> #include <vector> #include <array> #include <algorithm> #include <numeric> #include <iomanip> #include <unordered_set> #include <stack> #include <ext/pb_ds/assoc_container.hpp> #include <random> #include <chrono> //usings using namespace std; using namespace __gnu_pbds; // misc #define ll long long #define pb push_back #define pq priority_queue #define ub upper_bound #define lb lower_bound template<typename T, typename U> bool emin(T &a, const U &b){ return b < a ? a = b, true : false; } template<typename T, typename U> bool emax(T &a, const U &b){ return b > a ? a = b, true : false; } typedef uint64_t hash_t; // vectors #define vi vector<int> #define vvi vector<vi> #define vvvi vector<vvi> #define vpii vector<pair<int, int>> #define vvpii vector<vector<pair<int, int>>> #define vppipi vector<pair<int, pair<int, int>>> #define vl vector<ll> #define vvl vector<vl> #define vvvl vector<vvl> #define vpll vector<pair<ll, ll>> #define vb vector<bool> #define vvb vector<vb> #define vs vector<string> #define sz(x) (int)x.size() #define rz resize #define all(x) x.begin(), x.end() // pairs #define pii pair<int, int> #define pll pair<ll, ll> #define mp make_pair #define f first #define s second // sets #define si set<int> #define sl set<ll> #define ss set<string> #define in insert template <class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // maps #define mii map<int, int> #define mll map<ll, ll> // loops #define FR(x, z, y) for (int x = z; x < y; x++) #define FRe(x, z, y) FR(x, z, y + 1) #define F(x, y) FR(x, 0, y) #define Fe(x, y) F(x, y + 1) #define A(x, y) for(auto &x : y) int Y, X; struct Xnode{ Xnode(int x, int y) : l(x), r(y), v(0), lc(NULL), rc(NULL) {} int l, r; ll v; Xnode *lc, *rc; }; struct Ynode{ Ynode() : kid(1, X), lc(NULL), rc(NULL) {} Xnode kid; Ynode *lc, *rc; } *root; ll gcd2(ll x, ll y){ if(y == 0) return x; return gcd2(y, x % y); } void upd2(Xnode *cur, int x, ll k){ int l = cur->l, r = cur->r, m = (l + r) / 2; if(l == r) { cur->v = k; return; } if(x <= m){ if(cur->lc == NULL) cur->lc = new Xnode(l, m); upd2(cur->lc, x, k); } else { if(cur->rc == NULL) cur->rc = new Xnode(m + 1, r); upd2(cur->rc, x, k); } cur->v = gcd2(cur->lc ? cur->lc->v : 0, cur->rc ? cur->rc->v : 0); } ll get2(Xnode *cur, int rl, int rr){ if(cur == NULL || cur->l > rr || cur->r < rl) return 0; if(rl <= cur->l && cur->r <= rr) return cur->v; return gcd2(get2(cur->lc, rl, rr), get2(cur->rc, rl, rr)); } void upd1(Ynode *cur, int l, int r, int y, int x, ll k){ if(l == r) { upd2(&cur->kid, x, k); return; } int m = (l + r) / 2; if(y <= m){ if(cur->lc == NULL) cur->lc = new Ynode; upd1(cur->lc, l, m, y, x, k); } else { if(cur->rc == NULL) cur->rc = new Ynode; upd1(cur->rc, m + 1, r, y, x, k); } } ll get1(Ynode *cur, int l, int r, int rl, int rr, int xl, int xr){ if(cur == NULL || r < rl || l > rr) return 0; if(rl <= l && r <= rr) get2(&cur->kid, xl, xr); int m = (l + r) / 2; return gcd2(get1(cur->lc, l, m, rl, rr, xl, xr), get1(cur->rc, m + 1, r, rl, rr, xl, xr)); } void init(int R, int C){ Y = R, X = C; root = new Ynode; } void update(int P, int Q, ll K){ P++; Q++; upd1(root, 1, Y, P, Q, K); } ll calculate(int P, int Q, int U, int V){ P++; Q++; U++; V++; return get1(root, 1, Y, 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...