oj.uz

Submission #153731

# Submission time Handle Problem Language Result Execution time Memory
153731 2019-09-15T14:42:34 Z youssefbou62 Game (IOI13_game) C++14
63 / 100
 5486 ms 256004 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,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 {
			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); 
	ll g=gcd2(get(nodeC,l(u)),get(nodeC,r(u))); 
	if( g )
	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(){
// 	// 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

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 636 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 400 KB Output is correct
6 Correct 5 ms 632 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 5 ms 732 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 2 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 1943 ms 61768 KB Output is correct
5 Correct 1760 ms 61648 KB Output is correct
6 Correct 2013 ms 60268 KB Output is correct
7 Correct 2115 ms 56828 KB Output is correct
8 Correct 1374 ms 31188 KB Output is correct
9 Correct 2009 ms 58032 KB Output is correct
10 Correct 1960 ms 57040 KB Output is correct
11 Correct 2 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 5 ms 732 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 5 ms 760 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 14 ms 504 KB Output is correct
12 Correct 3114 ms 35276 KB Output is correct
13 Correct 4418 ms 16804 KB Output is correct
14 Correct 1583 ms 6104 KB Output is correct
15 Correct 5397 ms 23308 KB Output is correct
16 Correct 701 ms 45292 KB Output is correct
17 Correct 2946 ms 29944 KB Output is correct
18 Correct 4238 ms 46408 KB Output is correct
19 Correct 3992 ms 46772 KB Output is correct
20 Correct 3691 ms 46440 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 5 ms 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 5 ms 760 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 4 ms 504 KB Output is correct
12 Correct 1951 ms 61752 KB Output is correct
13 Correct 1754 ms 61636 KB Output is correct
14 Correct 2001 ms 60360 KB Output is correct
15 Correct 2058 ms 56704 KB Output is correct
16 Correct 1342 ms 31196 KB Output is correct
17 Correct 2009 ms 58100 KB Output is correct
18 Correct 1897 ms 57024 KB Output is correct
19 Correct 3101 ms 35056 KB Output is correct
20 Correct 4357 ms 16772 KB Output is correct
21 Correct 1619 ms 6084 KB Output is correct
22 Correct 5381 ms 23320 KB Output is correct
23 Correct 696 ms 45132 KB Output is correct
24 Correct 3020 ms 29816 KB Output is correct
25 Correct 4401 ms 46612 KB Output is correct
26 Correct 3917 ms 47004 KB Output is correct
27 Correct 3745 ms 46432 KB Output is correct
28 Runtime error 5486 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 888 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 5 ms 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 5 ms 760 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 1956 ms 61800 KB Output is correct
13 Correct 1763 ms 61592 KB Output is correct
14 Correct 1968 ms 60460 KB Output is correct
15 Correct 2059 ms 56660 KB Output is correct
16 Correct 1347 ms 31112 KB Output is correct
17 Correct 2067 ms 58260 KB Output is correct
18 Correct 2012 ms 57148 KB Output is correct
19 Correct 3076 ms 35344 KB Output is correct
20 Correct 4366 ms 16724 KB Output is correct
21 Correct 1599 ms 6320 KB Output is correct
22 Correct 5413 ms 23296 KB Output is correct
23 Correct 742 ms 45048 KB Output is correct
24 Correct 3026 ms 29960 KB Output is correct
25 Correct 4291 ms 46792 KB Output is correct
26 Correct 4019 ms 46836 KB Output is correct
27 Correct 3887 ms 46416 KB Output is correct
28 Runtime error 5484 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -