| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 153718 |
2019-09-15T11:56:40 Z |
youssefbou62 |
Game (IOI13_game) |
C++14 |
|
2 ms |
376 KB |
#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,int,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 {
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
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 |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
