oj.uz

Submission #153603

# Submission time Handle Problem Language Result Execution time Memory
153603 2019-09-14T19:58:27 Z youssefbou62 Game (IOI13_game) C++14
63 / 100
 13000 ms 184880 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>>  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 376 KB Output is correct
2 Correct 4 ms 760 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 380 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 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 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 8820 ms 60208 KB Output is correct
5 Correct 12141 ms 60028 KB Output is correct
6 Correct 3429 ms 58836 KB Output is correct
7 Correct 3326 ms 55076 KB Output is correct
8 Correct 2319 ms 30480 KB Output is correct
9 Correct 3520 ms 56472 KB Output is correct
10 Correct 3434 ms 55480 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 256 KB Output is correct
2 Correct 4 ms 760 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 376 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 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 2463 ms 35128 KB Output is correct
13 Correct 5526 ms 16772 KB Output is correct
14 Correct 1388 ms 6060 KB Output is correct
15 Correct 7823 ms 23312 KB Output is correct
16 Correct 456 ms 45224 KB Output is correct
17 Correct 2384 ms 29976 KB Output is correct
18 Correct 3269 ms 46640 KB Output is correct
19 Correct 3448 ms 47004 KB Output is correct
20 Correct 3081 ms 46284 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 4 ms 760 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 2 ms 376 KB Output is correct
8 Correct 3 ms 380 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 508 KB Output is correct
12 Correct 8807 ms 60152 KB Output is correct
13 Correct 12125 ms 60240 KB Output is correct
14 Correct 3387 ms 58772 KB Output is correct
15 Correct 3316 ms 55252 KB Output is correct
16 Correct 2326 ms 30332 KB Output is correct
17 Correct 3647 ms 56464 KB Output is correct
18 Correct 3511 ms 55472 KB Output is correct
19 Correct 2443 ms 35188 KB Output is correct
20 Correct 5546 ms 16688 KB Output is correct
21 Correct 1406 ms 6132 KB Output is correct
22 Correct 7911 ms 23216 KB Output is correct
23 Correct 458 ms 45024 KB Output is correct
24 Correct 2382 ms 29808 KB Output is correct
25 Correct 3687 ms 46552 KB Output is correct
26 Correct 3053 ms 46796 KB Output is correct
27 Correct 3112 ms 46320 KB Output is correct
28 Execution timed out 13059 ms 184848 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 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 3 ms 376 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 360 KB Output is correct
9 Correct 5 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 8775 ms 60132 KB Output is correct
13 Correct 12119 ms 60028 KB Output is correct
14 Correct 3261 ms 58736 KB Output is correct
15 Correct 3283 ms 55100 KB Output is correct
16 Correct 2313 ms 30404 KB Output is correct
17 Correct 3587 ms 56372 KB Output is correct
18 Correct 3455 ms 55484 KB Output is correct
19 Correct 2475 ms 35084 KB Output is correct
20 Correct 5512 ms 16784 KB Output is correct
21 Correct 1386 ms 5976 KB Output is correct
22 Correct 7895 ms 23244 KB Output is correct
23 Correct 457 ms 45164 KB Output is correct
24 Correct 2400 ms 29688 KB Output is correct
25 Correct 3293 ms 46488 KB Output is correct
26 Correct 3139 ms 46752 KB Output is correct
27 Correct 3066 ms 46312 KB Output is correct
28 Execution timed out 13024 ms 184880 KB Time limit exceeded
29 Halted 0 ms 0 KB -