oj.uz

Submission #153604

# Submission time Handle Problem Language Result Execution time Memory
153604 2019-09-14T20:00:09 Z youssefbou62 Game (IOI13_game) C++14
63 / 100
 13000 ms 256000 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 ; 

const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
    int operator()(int x) const { return 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));
			// 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); 
	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;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 4 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 4 ms 632 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 760 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 400 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 8557 ms 60256 KB Output is correct
5 Correct 5571 ms 60052 KB Output is correct
6 Correct 3591 ms 58768 KB Output is correct
7 Correct 3593 ms 55096 KB Output is correct
8 Correct 2271 ms 30400 KB Output is correct
9 Correct 3070 ms 56364 KB Output is correct
10 Correct 2640 ms 55476 KB Output is correct
11 Correct 2 ms 376 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 4 ms 632 KB Output is correct
3 Correct 4 ms 760 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 424 KB Output is correct
9 Correct 4 ms 760 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 2577 ms 35056 KB Output is correct
13 Correct 4893 ms 16688 KB Output is correct
14 Correct 1399 ms 6180 KB Output is correct
15 Correct 6959 ms 23324 KB Output is correct
16 Correct 497 ms 45120 KB Output is correct
17 Correct 2620 ms 29756 KB Output is correct
18 Correct 3505 ms 46440 KB Output is correct
19 Correct 3049 ms 46672 KB Output is correct
20 Correct 3036 ms 46100 KB Output is correct
21 Correct 2 ms 252 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 4 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 4 ms 632 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 392 KB Output is correct
9 Correct 4 ms 688 KB Output is correct
10 Correct 3 ms 552 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 6147 ms 60004 KB Output is correct
13 Correct 4682 ms 60064 KB Output is correct
14 Correct 3520 ms 58712 KB Output is correct
15 Correct 2625 ms 55068 KB Output is correct
16 Correct 2179 ms 30324 KB Output is correct
17 Correct 3575 ms 56348 KB Output is correct
18 Correct 2736 ms 55468 KB Output is correct
19 Correct 2478 ms 34972 KB Output is correct
20 Correct 5007 ms 16688 KB Output is correct
21 Correct 1402 ms 6004 KB Output is correct
22 Correct 6720 ms 23160 KB Output is correct
23 Correct 467 ms 45076 KB Output is correct
24 Correct 2684 ms 29680 KB Output is correct
25 Correct 3349 ms 46524 KB Output is correct
26 Correct 3086 ms 46732 KB Output is correct
27 Correct 3020 ms 46324 KB Output is correct
28 Execution timed out 13019 ms 184884 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 392 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 2 ms 396 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 760 KB Output is correct
10 Correct 3 ms 480 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 8232 ms 60152 KB Output is correct
13 Correct 7560 ms 60144 KB Output is correct
14 Correct 2841 ms 58640 KB Output is correct
15 Correct 3380 ms 55108 KB Output is correct
16 Correct 2255 ms 30452 KB Output is correct
17 Correct 2808 ms 56508 KB Output is correct
18 Correct 3897 ms 55648 KB Output is correct
19 Correct 2460 ms 34876 KB Output is correct
20 Correct 5086 ms 16456 KB Output is correct
21 Correct 1369 ms 4964 KB Output is correct
22 Correct 6776 ms 21952 KB Output is correct
23 Correct 505 ms 43936 KB Output is correct
24 Correct 2433 ms 27936 KB Output is correct
25 Correct 3284 ms 44492 KB Output is correct
26 Correct 3195 ms 44600 KB Output is correct
27 Correct 2817 ms 43952 KB Output is correct
28 Execution timed out 13063 ms 256000 KB Time limit exceeded
29 Halted 0 ms 0 KB -