Submission #1202583

#TimeUsernameProblemLanguageResultExecution timeMemory
1202583Marco_EscandonGame (IOI13_game)C++20
80 / 100
2000 ms321536 KiB
#include "game.h" #include<bits/stdc++.h> using namespace std; 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 st1{ int n=1; struct asdf{ int a, b; ll v; }; vector<asdf> cad; void update(int node, int l, int r, int p, ll v) { if(l>p||r<p) return; if(l==r&&l==p) {cad[node].v=v;return;} int m=(l+r)/2; if(m>=p) { if(cad[node].a==-1) { cad[node].a=cad.size(); cad.push_back({-1,-1,0}); } update(cad[node].a,l,m,p,v); } if(m<p) { if(cad[node].b==-1) { cad[node].b=cad.size(); cad.push_back({-1,-1,0}); } update(cad[node].b,m+1,r,p,v); } ll temp=0; if(cad[node].a!=-1) temp=cad[cad[node].a].v; if(cad[node].b!=-1) temp=gcd2(temp,cad[cad[node].b].v); cad[node].v=temp; } void update(int p, ll v) { update(0,1,n,p,v); } ll query(int node, int l, int r, int a, int b) { if(l>b||r<a) return 0; if(l>=a&&r<=b) return cad[node].v; if(cad[node].a==-1&&cad[node].b==-1) return 0; int m=(l+r)/2; if(cad[node].b==-1) return query(cad[node].a,l,m,a,b); if(cad[node].a==-1) return query(cad[node].b,m+1,r,a,b); return gcd2(query(cad[node].a,l,m,a,b),query(cad[node].b,m+1,r,a,b)); } ll query(int a, int b) { return query(0,1,n,a,b); } void init() { n=1000000000; cad.push_back({-1,-1,0}); } }nulo; struct st2{ int n=1; struct asdf{ int a, b; st1 v; }; vector<asdf> cad; int p1; void update(int node, int l, int r, int p, ll v) { if(l>p||r<p) return; if(l==r&&l==p) {cad[node].v.update(p1,v);return;} if(cad[node].a==-1) { cad[node].a=cad.size(); cad.push_back({-1,-1,nulo}); cad[node].b=cad.size(); cad.push_back({-1,-1,nulo}); } int m=(l+r)/2; update(cad[node].a,l,m,p,v); update(cad[node].b,m+1,r,p,v); cad[node].v.update(p1,gcd2(cad[cad[node].a].v.query(p1,p1),cad[cad[node].b].v.query(p1,p1))); } void update(int p,int P, ll v) { p1=P; update(0,1,n,p,v); } int c,d; ll query(int node, int l, int r, int a, int b) { if(l>=a&&r<=b) return cad[node].v.query(c,d); if(l>b||r<a||cad[node].a==-1) return 0; int m=(l+r)/2; return gcd2(query(cad[node].a,l,m,a,b), query(cad[node].b,m+1,r,a,b)); } ll query(int a, int b,int C,int D) { c=C; d=D; return query(0,1,n,a,b); } void init() { n=1000000000; cad.push_back({-1,-1,nulo}); } }asd; void init(int R, int C) { nulo.init(); asd.init(); } void update(int P, int Q, long long K) { P++; Q++; asd.update(P,Q,K); } long long calculate(int P, int Q, int U, int V) { P++; Q++; U++; V++; ll ans=asd.query(P,U,Q,V); return ans; }
#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...