Submission #136857

#TimeUsernameProblemLanguageResultExecution timeMemory
136857JuneyGame (IOI13_game)C++14
63 / 100
3339 ms256004 KiB
#include "game.h" #include <bits/stdc++.h> using namespace std; #define MAX_RANGE 1000000000 #define QUERY_SIZE 22000 #define gcd(x, y) gcd2(x, y) 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 CNODE { int l, r; ll val; CNODE() : l(0), r(0), val(0) {} }; vector<CNODE> CT; struct CDST { void update(int y, ll val, int l, int r, int n) { if(l == r) { CT[n].val = val; return; } int mid = (l + r) >> 1; if(y <= mid) { if(CT[n].l == 0) CT[n].l = CT.size(), CT.push_back(CNODE()); update(y, val, l, mid , CT[n].l); } else { if(CT[n].r == 0) CT[n].r = CT.size(), CT.push_back(CNODE()); update(y, val, mid+1, r, CT[n].r); } CT[n].val = gcd(CT[CT[n].l].val, CT[CT[n].r].val); } void update(int y, ll val, int n) { update(y, val, 1, MAX_RANGE, n); } ll query(int c1, int c2, int l, int r, int n) { if(n == 0 || r < c1 || c2 < l) return 0; if(c1 <= l && r <= c2) return CT[n].val; int mid = (l + r) >> 1; return gcd(query(c1, c2, l, mid, CT[n].l), query(c1, c2, mid+1, r, CT[n].r)); } ll query(int c1, int c2, int n) { return query(c1, c2, 1, MAX_RANGE, n); } } cdst; struct RNODE { int l, r, croot; int get_root() { if(croot == 0) croot = CT.size(), CT.push_back(CNODE()); return croot; } RNODE() : l(0), r(0), croot(0) {} }; vector<RNODE> RT; struct RDST { void mrg(int y, int n, int ln, int rn, int l=1, int r=MAX_RANGE) { if(ln == 0 && rn == 0) return; CT[n].val = gcd(CT[ln].val, CT[rn].val); if(l == r) return; int mid = (l + r) >> 1; if(y <= mid) { if(CT[n].l == 0) CT[n].l = CT.size(), CT.push_back(CNODE()); mrg(y, CT[n].l, CT[ln].l, CT[rn].l, l, mid); } else { if(CT[n].r == 0) CT[n].r = CT.size(), CT.push_back(CNODE()); mrg(y, CT[n].r, CT[ln].r, CT[rn].r, mid+1, r); } } void update(int x, int y, ll val, int l=1, int r=MAX_RANGE, int n=1) { if(l == r) { cdst.update(y, val, RT[n].get_root()); return; } int mid = (l + r) >> 1; if(x <= mid) { if(RT[n].l == 0) RT[n].l = RT.size(), RT.push_back(RNODE()); update(x, y, val, l, mid, RT[n].l); } else { if(RT[n].r == 0) RT[n].r = RT.size(), RT.push_back(RNODE()); update(x, y, val, mid+1, r, RT[n].r); } mrg(y, RT[n].get_root(), RT[RT[n].l].get_root(), RT[RT[n].r].get_root()); } ll query(int r1, int c1, int r2, int c2, int l=1, int r=MAX_RANGE, int n=1) { if(n == 0 || r < r1 || r2 < l) return 0; if(r1 <= l && r <= r2) return cdst.query(c1, c2, RT[n].get_root()); int mid = (l + r) >> 1; return gcd(query(r1, c1, r2, c2, l, mid, RT[n].l), query(r1, c1, r2, c2, mid+1, r, RT[n].r)); } } dst; void init(int R, int C) { CT.push_back(CNODE()); RT.push_back(RNODE()); RT.push_back(RNODE()); } void update(int P, int Q, long long K) { dst.update(P+1, Q+1, K); } long long calculate(int P, int Q, int U, int V) { return dst.query(P+1, Q+1, U+1, V+1); }

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