Submission #153733

#TimeUsernameProblemLanguageResultExecution timeMemory
153733youssefbou62Game (IOI13_game)C++14
0 / 100
5 ms760 KiB
#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 ; struct chash { const int RANDOM = (long long)(make_unique<char>().get()) ^ chrono::high_resolution_clock::now().time_since_epoch().count(); static unsigned long long hash_f(unsigned long long x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } static unsigned hash_combine(unsigned a, unsigned b) { return a * 31 + b; } int operator()(int x) const { return hash_f(x)^RANDOM; } }; const int N = 2005; gp_hash_table<int,gp_hash_table<int,ll,chash>,chash> 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 { ll g = gcd2(get(l(nodeC),(u)),get(r(nodeC),u)); if( g ) st[nodeC][u]= g; } // 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); ll g=gcd2(get(nodeC,l(u)),get(nodeC,r(u))); if( g ) st[nodeC][u] = g; } 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(){ // // cout << (sizeof (st)) << endl; // 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; // } // } // // cout << (sizeof (st)) << 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 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...