Submission #1030035

#TimeUsernameProblemLanguageResultExecution timeMemory
1030035tolbiGame (IOI13_game)C++17
0 / 100
3 ms856 KiB
#include "game.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; 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; } mt19937_64 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count()); struct Treap{ struct Node{ Node *lnode, *rnode; ll val, gg, h; int pos; Node(int pos, ll x):val(x),gg(x),h(ayahya()),pos(pos),lnode(nullptr),rnode(nullptr){} } *root; Treap():root(nullptr){} void upd(Node* nd){ nd->gg=nd->val; if (nd->lnode) nd->gg=gcd2(nd->lnode->gg,nd->gg); if (nd->rnode) nd->gg=gcd2(nd->rnode->gg,nd->gg); } Node* merge(Node* a, Node* b){ if (!a || !b) return (a?a:b); if (a->h > b->h) return a->rnode = merge(a->rnode,b),upd(a),a; return b->lnode = merge(a,b->lnode),upd(b),b; } pair<Node*, Node*> split(Node* node, int x){ if (!node) return {nullptr,nullptr}; if (node->pos>=x){ pair<Node*, Node*> spl = split(node->lnode,x); node->lnode=spl.second; upd(node); return {spl.first,node}; } pair<Node*, Node*> spl = split(node->rnode,x); node->rnode=spl.first; upd(node); return {node,spl.second}; } void update(int x, ll val){ if (root==nullptr){ return root = new Node(x,val), void(23); } Node* nd = root; while (nd){ if (nd->pos==x) break; if (nd->pos>x) nd=nd->lnode; else nd=nd->rnode; } if (nd==nullptr){ Node* nnode = new Node(x,val); pair<Node*, Node*> spl = split(root,x); root=merge(spl.first,nnode); root=merge(root,spl.second); } else { vector<Node*> backtrack; nd->val=val; upd(nd); nd = root; while (nd->pos!=x){ backtrack.push_back(nd); if (nd->pos>x) nd=nd->lnode; else nd=nd->rnode; } while (backtrack.size()){ upd(backtrack.back()); backtrack.pop_back(); } } } ll query(int l, int r){ pair<Node*, Node*> spl = split(root, l); pair<Node*, Node*> spl2 = split(spl.second, r+1); ll ret = 0; if (spl2.first) ret = spl2.first->gg; root = merge(spl2.first,spl2.second); root = merge(spl.first,root); return ret; } }; constexpr int MAXN = 1000000000; struct SegTree{ struct Node{ Node *lnode, *rnode; Treap tr; Node():lnode(nullptr),rnode(nullptr){} } *root; SegTree():root(new Node){} void update(int x, int y, ll val){ int l = 0, r = MAXN; Node *node = root; while (l<r){ int mid = l+(r-l)/2; node->tr.update(y,val); if (mid>=x){ r=mid; if (node->lnode==nullptr) node->lnode = new Node; node=node->lnode; } else { l=mid+1; if (node->rnode==nullptr) node->rnode = new Node; node=node->rnode; } } node->tr.update(y,val); } ll query(int tl, int tr, int a, int b, int l = 0, int r = MAXN, Node* node = nullptr){ if (l==0 && r==MAXN) node=root; if (l>=tl && r<=tr) return node->tr.query(a,b); if (l>tr || r<tl) return 0; int mid = l+(r-l)/2; ll ret = 0; if (node->lnode && mid>=tl) ret=gcd2(ret,query(tl,tr,a,b,l,mid,node->lnode)); if (node->rnode && mid<tr) ret=gcd2(ret,query(tl,tr,a,b,mid+1,r,node->rnode)); return ret; } } segtree; void init(int R, int C) { //23 severim } void update(int P, int Q, long long K) { segtree.update(P,Q,K); } long long calculate(int P, int Q, int U, int V) { return segtree.query(P,U,Q,V); }

Compilation message (stderr)

game.cpp: In constructor 'Treap::Node::Node(int, ll)':
game.cpp:19:7: warning: 'Treap::Node::pos' will be initialized after [-Wreorder]
   19 |   int pos;
      |       ^~~
game.cpp:17:9: warning:   'Treap::Node* Treap::Node::lnode' [-Wreorder]
   17 |   Node *lnode, *rnode;
      |         ^~~~~
game.cpp:20:3: warning:   when initialized here [-Wreorder]
   20 |   Node(int pos, ll x):val(x),gg(x),h(ayahya()),pos(pos),lnode(nullptr),rnode(nullptr){}
      |   ^~~~
#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...