Submission #38637

#TimeUsernameProblemLanguageResultExecution timeMemory
38637alenam0161Game (IOI13_game)C++14
80 / 100
13000 ms141544 KiB
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <cstring> #include "game.h" #define pn node* #define ps segtree* using namespace std; const int N = 1e9; 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; } struct node { ll val; int key;//index int prior; ll ans_tree; node *l, *r; node(int _X = 0, ll valu = 0ll) { key = _X; val = valu; ans_tree = val; prior = rand(); l = r = NULL; } }; inline void upd_ans(pn &t) { if (t) {t->ans_tree = gcd2(t->val,gcd2(t->l ? t->l->ans_tree : 0ll, t->r ? t->r->ans_tree : 0ll)); } } void split(pn t, pn &l, pn &r, int key) { if (!t) { l = r = NULL; return; } if (t->key > key) { split(t->l, l, t->l, key); r = t; } else { split(t->r, t->r, r, key); l = t; } upd_ans(l); upd_ans(r); } void merge(pn &t, pn l, pn r) { if (!l || !r) { t = l ? l : r; } else { if (l->prior > r->prior) { merge(l->r, l->r, r); t = l; } else { merge(r->l, l, r->l); t = r; } } upd_ans(t); } void insert(pn &t, pn it) { if (!t) { t = it; } else { if (t->prior < it->prior) { split(t, it->l, it->r, it->key); t = it; } else{ if (t->key > it->key) { insert(t->l, it); } else insert(t->r, it); } } upd_ans(t); } void erase(pn &t, int key) { if (!t)return; if (t->key == key) { merge(t, t->l, t->r); } else { if (t->key > key)erase(t->l, key); else erase(t->r, key); } upd_ans(t); } struct segtree { node *down; segtree *l, *r; segtree(node *U = NULL) { down = U; l = r = NULL; } }; ps root; ps next_sg() { static segtree SEG[2000 * 1000]; static int c1 = 0; return &SEG[c1++]; } pn next_node() { static node an[2000 * 1000]; static int c2 = 0; return &an[c2++]; } void init(int R, int C) { /* ... */ srand(2781); } void printt(pn t, int lv = 0) { if (!t)return; printt(t->l, lv + 1); cout <<" LEVEL "<<lv<<" "<< t->val << " " << t->ans_tree << " " << t->key << " " << t->prior << endl; printt(t->r, lv + 1); } ll get_ans(pn t, int key) { if (!t)return 0ll; if (t->key == key)return t->val; else { if (t->key > key) { return get_ans(t->l, key); } else return get_ans(t->r, key); } } void update_sg(int x, int y, long long vl, ps& t, int l, int r) { if (!t) { t = next_sg(); } if (l == r) { erase(t->down, y); pn cur = new node(y, vl); insert(t->down, cur); } else { int m = (l + r) / 2; if (x <= m)update_sg(x, y, vl, t->l, l, m); else update_sg(x, y, vl, t->r, m + 1, r); ll a1 = t->l ? get_ans(t->l->down, y):0ll; ll a2 = t->r ? get_ans(t->r->down, y):0ll; erase(t->down, y); pn cur = new node(y, gcd2(a1,a2)); insert(t->down, cur); } } void update(int P, int Q, long long K) { update_sg(P, Q, K,root, 0, N); } long long query_y(int l, int r, pn t) { if (!t)return 0ll; pn tl; pn tr; split(t, tl, t, l - 1); split(t, t, tr, r); long long ans = t ? t->ans_tree:0ll; merge(t, tl, t); merge(t, t, tr); return ans; } long long query_x(int xx, int xy, int yx, int yy, ps t, int l, int r) { if (!t)return 0ll; if (xx <= l&&r <= xy) { return query_y(yx, yy, t->down); } else { int m = (l + r) / 2; long long cur = 0; if (xx <= m)cur = gcd2(cur,query_x(xx, xy, yx, yy, t->l, l, m)); if (xy> m)cur = gcd2(cur, query_x(xx, xy, yx, yy, t->r, m+1, r)); return cur; } } long long calculate(int P, int Q, int U, int V) { return query_x(P,U,Q,V,root,0,N); }

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^
#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...