This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "game.h"
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
using ll = long long ;
const int N = 2005;
gp_hash_table<int,gp_hash_table<int,ll>> st;
int ROW , COL ;
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;
}
int l(int u){return (u*2+1);}
int r(int u ){return (u*2+2);}
void init(int n, int m){
ROW = n ;
COL = m ;
}
ll get(int C , int R ){
if( st.find(C)!=st.end()){
if( st[C].find(R) != st[C].end() )return st[C][R];
}return 0;
}
void updateColumn(int nodeC , int row , int L , int R , int u ,bool isleaf, ll val ){
if( L == R ){
// cout << isleaf<<"before update="<<st[nodeC][u]<<endl;
if( isleaf )
st[nodeC][u]=val ;
else st[nodeC][u] = gcd2(get(l(nodeC),(u)),get(r(nodeC),u));
// cout << "after update="<<st[nodeC][u]<<endl;
return ;
}
int mid = (L+R)/2 ;
if( row <= mid )updateColumn(nodeC,row,L,mid,l(u),isleaf,val);
else updateColumn(nodeC,row,mid+1,R,r(u),isleaf,val);
st[nodeC][u] = gcd2(get(nodeC,l(u)),get(nodeC,r(u)));
}
void UPDATE(int nodeC,int row,int Column ,int L , int R , ll val ){
if( L != R ){
int mid = (L+R)/2 ;
if( Column <= mid )
UPDATE(l(nodeC),row,Column,L,mid,val);
else UPDATE(r(nodeC),row,Column,mid+1,R,val);
}
updateColumn(nodeC,row,0,ROW-1,0,(L==R),val);
}
ll queryColumn(int nodeC , int qlR, int qrR , int L , int R , int u=0 ){
// cout << " u = "<<u<<" l(u)= "<<l(u)<<" r= "<<r(u) << endl;
if( L >= qlR && R <= qrR ){
// cout << L << " " << R << " COL = "<<st[nodeC][u]<<endl;
return get(nodeC,u);
}
int mid = (L+R)/2;
if( L > qrR || R < qlR || L > R)return 0;
return gcd2(queryColumn(nodeC,qlR,qrR,L,mid,l(u)),queryColumn(nodeC,qlR,qrR,mid+1,R,r(u)));
}
ll QUERY (int qlR , int qrR , int qlC , int qrC , int L , int R , int u=0 )
{
// cout << qlC << " " << qrC << endl;
if( L >= qlC && R <= qrC){
// cout << qlR << " " << qrR<<" | " <<" L = "<<L<<" R="<<R<<" quer = "<<queryColumn(u,qlR,qrR,0,ROW-1)<<endl;
return queryColumn(u,qlR,qrR,0,ROW-1);
}
if( L > qrC || R < qlC || L > R)return 0;
int mid = (L+R)/2;
return gcd2(QUERY(qlR , qrR , qlC , qrC , L , mid , l(u)),QUERY(qlR , qrR , qlC , qrC ,mid+1, R, r(u))) ;
}
void update(int P , int Q , ll val ){
// p is row
UPDATE(0,P,Q,0,COL-1,val);
}
ll calculate(int P , int Q , int U , int V){
return QUERY(P,U,Q,V,0,COL-1);
}
// int main(){
// int n , m , X ;
// cin >> n >> m >> X;
// init(n,m);
// for(int i = 0 ; i < X ; i++ ){
// int type ;
// cin >> type ;
// if( type == 1 ){
// int P, Q ; ll K ;
// cin >> P >> Q >> K ; //cout << "UPDATE *******"<<endl;
// update(P,Q,K);
// }else {
// int P,Q,U,V;
// cin >> P >> Q >> U >> V;
// // cout <<"***********"<<endl;
// cout << calculate(P,Q,U,V)<<endl;
// }
// }
// }
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |