Submission #24229

#TimeUsernameProblemLanguageResultExecution timeMemory
24229Parthib_GuptaGame (IOI13_game)C++14
36 / 100
3256 ms229836 KiB
#include "game.h" #include "bits/stdc++.h" typedef long long vlong; 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; } long long r , c ; long long tree[2700 * 2][2 * 2700]; vlong qy(vlong ndx, vlong ndy, vlong st, vlong ed,vlong y1,vlong y2) { if(y2 < st || y1 > ed) return 0; if(y2 >= ed && y1 <= st){ return tree[ndx][ndy]; } vlong md = (st+ed)/2; vlong v1 = qy(ndx, 2*ndy, st, md, y1, y2); vlong v2 = qy(ndx, 2*ndy + 1, md+ 1, ed, y1, y2); return gcd2(v1, v2); } vlong qx(vlong nd, vlong st, vlong ed, vlong x1, vlong y1, vlong x2, vlong y2) { if(ed < x1 || st > x2) return 0; if(x1 <= st && ed <= x2){ return qy(nd, 1, 0, c-1, y1, y2); } vlong md = (st+ed)/2; vlong v1 = qx(2*nd, st, md, x1, y1, x2, y2); vlong v2 = qx(2*nd + 1, md+1, ed, x1, y1, x2, y2); return gcd2(v1, v2); } void up_y(vlong ndx, vlong lx, vlong rx, vlong nd, vlong st, vlong ed, vlong y, vlong nVal) { if(st == ed){ if(lx == rx){ tree[ndx][nd] = nVal; } else{ tree[ndx][nd] = gcd2(tree[ndx*2][nd], tree[ndx*2 + 1][nd]); } return; } vlong md = (st+ed)/2; if(y <= md) up_y(ndx, lx, rx, nd*2, st, md, y, nVal); else up_y(ndx, lx, rx, nd*2 + 1, md + 1, ed, y, nVal); tree[ndx][nd] = gcd2(tree[ndx][nd*2], tree[ndx][nd*2 + 1]); } void up_x(vlong nd, vlong st, vlong ed, vlong x, vlong y, vlong nVal) { // cerr << "I am here\n"; if(st != ed){ vlong md = (st+ed)/2; if(x <= md) up_x(2*nd, st, md, x, y, nVal); else up_x(2*nd + 1, md+1, ed, x, y, nVal); } up_y(nd, st, ed, 1, 0, c-1, y, nVal); } void build_Y(vlong nx, vlong sx, vlong ex, vlong nd, vlong st, vlong ed) { if(st == ed){ if(sx == ex){ tree[nx][nd] = 0; } else{ tree[nx][nd] = gcd2(tree[nx*2][nd], tree[nx*2 + 1][nd]); } return; } vlong md = (st+ed)/2; build_Y(nx, sx, ex, 2*nd, st, md); build_Y(nx, sx, ex, 2*nd + 1, md+1, ed); tree[nx][nd] = gcd2(tree[nx][2*nd], tree[nx][2*nd + 1]); } void build_X(vlong nd, vlong st, vlong ed) { if(st != ed){ vlong md = (st+ed)/2; build_X(2*nd, st, md); build_X(2*nd + 1, md + 1, ed); } build_Y(nd, st, ed, 1, 0, c-1); } void init(int R, int C) { r = R; c = C; build_X(1, 0, R-1); } void update(int P, int Q, long long K) { up_x(1, 0, r-1, P, Q, K); } long long calculate(int P, int Q, int U, int V) { return qx(1, 0, r-1, P, Q, U, 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...