Submission #30038

#TimeUsernameProblemLanguageResultExecution timeMemory
30038cdemirerGame (IOI13_game)C++14
63 / 100
3496 ms143428 KiB
#include "game.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> llp; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<vi> vvi; typedef vector<vii> vvii; #define pb(x) push_back(x) #define mp(x, y) make_pair(x, y) 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; } int R, C; typedef struct Node_o_ { int l, r; int inner; ll val; } Node_o; typedef struct Node_i_ { int l, r; ll val; } Node_i; #define oleft(x) (rez_o[(x)].l) #define oright(x) (rez_o[(x)].r) #define ileft(x) (rez_i[(x)].l) #define iright(x) (rez_i[(x)].r) const int MAXN = 1073741823; Node_o rez_o[700000]; int roc = 1; Node_i rez_i[8000000]; int ric = 1; int root; int createNode_o() { rez_o[roc].l = rez_o[roc].r = rez_o[roc].inner = rez_o[roc].val = 0; return roc++; } int createNode_i() { rez_i[ric].l = rez_i[ric].r = rez_i[ric].val = 0; return ric++; } ll get_i(int x, int l, int r, int cl, int cr) { int mid = (cl+cr)/2; if (l == cl && r == cr) return rez_i[x].val; else if (l > mid) { if (!iright(x)) return 0; return get_i(iright(x), l, r, mid+1, cr); } else if (r <= mid) { if (!ileft(x)) return 0; return get_i(ileft(x), l, r, cl, mid); } else { ll a, b; if (!ileft(x)) a = 0; else a = get_i(ileft(x), l, mid, cl, mid); if (!iright(x)) b = 0; else b = get_i(iright(x), mid+1, r, mid+1, cr); return gcd2(a, b); } } ll get_o(int x, int l, int r, int cl, int cr, int li, int ri) { int mid = (cl+cr)/2; if (l == cl && r == cr) { if (!rez_o[x].inner) rez_o[x].inner = createNode_i(); return get_i(rez_o[x].inner, li, ri, 0, MAXN); } else if (l > mid) { if (!oright(x)) return 0; return get_o(oright(x), l, r, mid+1, cr, li, ri); } else if (r <= mid) { if (!oleft(x)) return 0; return get_o(oleft(x), l, r, cl, mid, li, ri); } else { ll a, b; if (!oleft(x)) a = 0; else a = get_o(oleft(x), l, mid, cl, mid, li, ri); if (!oright(x)) b = 0; else b = get_o(oright(x), mid+1, r, mid+1, cr, li, ri); return gcd2(a, b); } } void update_i(int x, int p, int cl, int cr, ll u) { int mid = (cl+cr)/2; if (p == cl && p == cr) { rez_i[x].val = u; } else if (p > mid) { if (!iright(x)) iright(x) = createNode_i(); update_i(iright(x), p, mid+1, cr, u); rez_i[x].val = gcd2(rez_i[ileft(x)].val, rez_i[iright(x)].val); } else if (p <= mid) { if (!ileft(x)) ileft(x) = createNode_i(); update_i(ileft(x), p, cl, mid, u); rez_i[x].val = gcd2(rez_i[ileft(x)].val, rez_i[iright(x)].val); } } void update_o(int x, int po, int pi, int cl, int cr, ll u) { int mid = (cl+cr)/2; if (po == cl && po == cr) { if (!rez_o[x].inner) rez_o[x].inner = createNode_i(); update_i(rez_o[x].inner, pi, 0, MAXN, u); } else if (po > mid) { if (!oright(x)) oright(x) = createNode_o(); update_o(oright(x), po, pi, mid+1, cr, u); ll nv = gcd2(get_i(rez_o[oleft(x)].inner, pi, pi, 0, MAXN), get_i(rez_o[oright(x)].inner, pi, pi, 0, MAXN)); if (!rez_o[x].inner) rez_o[x].inner = createNode_i(); update_i(rez_o[x].inner, pi, 0, MAXN, nv); } else if (po <= mid) { if (!oleft(x)) oleft(x) = createNode_o(); update_o(oleft(x), po, pi, cl, mid, u); ll nv = gcd2(get_i(rez_o[oleft(x)].inner, pi, pi, 0, MAXN), get_i(rez_o[oright(x)].inner, pi, pi, 0, MAXN)); if (!rez_o[x].inner) rez_o[x].inner = createNode_i(); update_i(rez_o[x].inner, pi, 0, MAXN, nv); } } void init(int _R, int _C) { R = _R; C = _C; root = createNode_o(); } void update(int P, int Q, long long K) { update_o(root, P, Q, 0, MAXN, K); } long long calculate(int P, int Q, int U, int V) { return get_o(root, P, U, 0, MAXN, Q, V); }

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...