Submission #1025562

#TimeUsernameProblemLanguageResultExecution timeMemory
1025562socpiteGame (IOI13_game)C++98
63 / 100
1079 ms256000 KiB
#include <bits/stdc++.h> using namespace std; #include "game.h" const int maxn = 1e9; 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 st1d{ st1d *lc, *rc; long long val; st1d(): val(0), lc(nullptr), rc(nullptr){} void add(int y, long long p, int l = 0, int r = maxn){ if(l == r){ val = p; return; } int mid = (l+r)>>1; if(y <= mid){ if(!lc)lc = new st1d(); lc->add(y, p, l, mid); if(rc)val = gcd2(lc->val, rc->val); else val = lc->val; } else { if(!rc)rc = new st1d(); rc->add(y, p, mid+1, r); if(lc)val = gcd2(lc->val, rc->val); else val = rc->val; } } void cpy(st1d &b, int y, int l = 0, int r = maxn){ val = b.val; if(l == r)return; int mid = (l+r)>>1; if(y <= mid){ if(!lc)lc = new st1d(); lc->cpy(*b.lc, y, l, mid); } else { if(!rc)rc = new st1d(); rc->cpy(*b.rc, y, mid+1, r); } } void merge(st1d &bl, st1d &br, int y, int l = 0, int r = maxn){ val = gcd2(bl.val, br.val); if(l == r)return; int mid = (l+r)>>1; if(y <= mid){ if(!lc)lc = new st1d(); if(!bl.lc)lc->cpy(*br.lc, y, l, mid); else if(!br.lc)lc->cpy(*bl.lc, y, l, mid); else lc->merge(*bl.lc, *br.lc, y, l, mid); } else { if(!rc)rc = new st1d(); if(!bl.rc)rc->cpy(*br.rc, y, mid+1, r); else if(!br.rc)rc->cpy(*bl.rc, y, mid+1, r); else rc->merge(*bl.rc, *br.rc, y, mid+1, r); } } long long query(int ql, int qr, int l = 0, int r = maxn){ if(ql > r || l > qr)return 0; if(ql <= l && r <= qr)return val; int mid = (l+r)>>1; long long lhs = lc ? lc->query(ql, qr, l, mid) : 0, rhs = rc ? rc->query(ql, qr, mid+1, r) : 0; return gcd2(lhs, rhs); } }; struct st2d{ st2d *lc, *rc; int l, r; st1d st; st2d(int _l, int _r): st(), l(_l), r(_r), lc(nullptr), rc(nullptr){} void add(int x, int y, long long p){ if(l == r){ st.add(y, p); return; } int mid = (l+r)>>1; if(x <= mid){ if(!lc)lc = new st2d(l, mid); lc->add(x, y, p); if(rc)st.merge(lc->st, rc->st, y); else st.cpy(lc->st, y); } else { if(!rc)rc = new st2d(mid+1, r); rc->add(x, y, p); if(lc)st.merge(lc->st, rc->st, y); else st.cpy(rc->st, y); } } long long query(int p, int q, int u, int v){ if(l > u || r < p)return 0; if(p <= l && r <= u)return st.query(q, v); long long lhs = lc ? lc->query(p, q, u, v) : 0, rhs = rc ? rc->query(p, q, u, v) : 0; return gcd2(lhs, rhs); } }rt(0, maxn); void init(int R, int C) { } void update(int P, int Q, long long K) { rt.add(P, Q, K); } long long calculate(int P, int Q, int U, int V) { /* ... */ return rt.query(P, Q, U, V); }

Compilation message (stderr)

game.cpp: In constructor 'st1d::st1d()':
game.cpp:20:15: warning: 'st1d::val' will be initialized after [-Wreorder]
   20 |     long long val;
      |               ^~~
game.cpp:19:11: warning:   'st1d* st1d::lc' [-Wreorder]
   19 |     st1d *lc, *rc;
      |           ^~
game.cpp:21:5: warning:   when initialized here [-Wreorder]
   21 |     st1d(): val(0), lc(nullptr), rc(nullptr){}
      |     ^~~~
game.cpp: In constructor 'st2d::st2d(int, int)':
game.cpp:84:10: warning: 'st2d::st' will be initialized after [-Wreorder]
   84 |     st1d st;
      |          ^~
game.cpp:83:9: warning:   'int st2d::l' [-Wreorder]
   83 |     int l, r;
      |         ^
game.cpp:85:5: warning:   when initialized here [-Wreorder]
   85 |     st2d(int _l, int _r): st(), l(_l), r(_r), lc(nullptr), rc(nullptr){}
      |     ^~~~
game.cpp:83:12: warning: 'st2d::r' will be initialized after [-Wreorder]
   83 |     int l, r;
      |            ^
game.cpp:82:11: warning:   'st2d* st2d::lc' [-Wreorder]
   82 |     st2d *lc, *rc;
      |           ^~
game.cpp:85:5: warning:   when initialized here [-Wreorder]
   85 |     st2d(int _l, int _r): st(), l(_l), r(_r), lc(nullptr), rc(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...