제출 #281936

#제출 시각아이디문제언어결과실행 시간메모리
281936shayan_p게임 (IOI13_game)C++14
37 / 100
13087 ms9064 KiB
// And you curse yourself for things you never done #include<bits/stdc++.h> #include "game.h" #define F first #define S second #define PB push_back #define sz(s) int((s).size()) #define bit(n,k) (((n)>>(k))&1) using namespace std; typedef long long ll; typedef pair<int,int> pii; int N, M; struct node{ ll g = 0, x = 0; node *L = 0, *R = 0; int pos = 0, S = 0; node(int _pos, ll _g){ pos = _pos, g = _g, x = _g; S = 1; } void rest(int _pos, ll _g){ pos = _pos, g = _g, x = _g; S = 1; } ll ask(int _pos){ if(pos == _pos) return x; if(_pos < pos) return (L ? L->ask(_pos) : 0); else return (R ? R->ask(_pos) : 0); } }; void build(node* nw){ nw->S = (nw->L ? nw->L->S : 0) + (nw->R ? nw->R->S : 0) + 1; nw->g = __gcd(nw->x, __gcd( nw->L ? nw->L->g : 0, nw->R ? nw->R->g : 0 )); } pair<node*, node*> split(node* nw, int x){ if(nw == 0) return {0, 0}; if(nw->pos < x){ auto it = split(nw->R, x); nw->R = it.F; build(nw); return {nw, it.S}; } else{ auto it = split(nw->L, x); nw->L = it.S; build(nw); return {it.F, nw}; } assert(0); } node* merge(node *A, node *B){ if(A == 0) return B; if(B == 0) return A; if((rand() % (A->S + B->S)) < A->S){ A->R = merge(A->R, B); build(A); return A; } else{ B->L = merge(A, B->L); build(B); return B; } assert(0); } pair<node*, ll> _ask(node *nw, int f, int s){ assert(nw); auto A = split(nw, f); auto B = split(A.S, s); ll ans = (B.F ? B.F->g : 0); return {merge(A.F, merge(B.F, B.S)), ans}; } node* _put(node *nw, int pos, ll x){ // assert(nw); auto A = split(nw, pos); auto B = split(A.S, pos+1); node* r = B.F; if(r == 0) r = new node(pos, x); else r->rest(pos, x); return merge(A.F, merge(r, B.S)); } struct node2{ node* g = 0; node2 *L = 0, *R = 0; void put(int posx, int posy, ll x, int l = 0, int r = N){ ll num = x; if(r-l > 1){ int mid = (l+r) >> 1; if(posx < mid){ if(!L) L = new node2(); L->put(posx, posy, x, l, mid); } else{ if(!R) R = new node2(); R->put(posx, posy, x, mid, r); } num = __gcd(L ? L->g->ask(posy) : 0, R ? R->g->ask(posy) : 0); } if(!g) g = new node(posy, num); else g = _put(g, posy, num); } ll ask(int f, int s, int ff, int ss, int l = 0, int r = N){ if(r <= f || s <= l) return 0; if(f <= l && r <= s){ if(!g) return 0; auto it = _ask(g, ff, ss); g = it.F; return it.S; } int mid = (l+r) >> 1; return __gcd(L ? L->ask(f, s, ff, ss, l, mid) : 0, R ? R->ask(f, s, ff, ss, mid, r) : 0); } }; node2* root; void init(int N, int M){ srand(time(0)); ::N = N, ::M = M; root = new node2(); } map<int, node*> mp; void update(int x, int y, ll w){ if(mp.count(x) == 0) mp[x] = new node(y, w); else mp[x] = _put(mp[x], y, w); // root->put(x, y, w); } ll calculate(int x, int y, int xx, int yy){ vector<pair<int, node*> > tmp; ll ans = 0; for(auto it : mp){ if(x <= it.F && it.F <= xx){ auto x = _ask(it.S, y, yy+1); ans = __gcd(ans, x.S); tmp.PB({it.F, x.F}); } } for(auto it : tmp){ mp[it.F] = it.S; } return ans; // return root->ask(x, ++xx, y, ++yy); }

컴파일 시 표준 에러 (stderr) 메시지

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