oj.uz

Submission #153592

# Submission time Handle Problem Language Result Execution time Memory
153592 2019-09-14T19:19:25 Z youssefbou62 Game (IOI13_game) C++14
63 / 100
 13000 ms 185004 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 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));  		
		// 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 5 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 380 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 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 376 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 8904 ms 60216 KB Output is correct
5 Correct 12307 ms 60200 KB Output is correct
6 Correct 3393 ms 58844 KB Output is correct
7 Correct 3411 ms 55124 KB Output is correct
8 Correct 2263 ms 30332 KB Output is correct
9 Correct 3733 ms 56500 KB Output is correct
10 Correct 3551 ms 55484 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 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 2449 ms 35088 KB Output is correct
13 Correct 5527 ms 16788 KB Output is correct
14 Correct 1400 ms 6188 KB Output is correct
15 Correct 7904 ms 23416 KB Output is correct
16 Correct 452 ms 45128 KB Output is correct
17 Correct 2435 ms 29832 KB Output is correct
18 Correct 3282 ms 46520 KB Output is correct
19 Correct 3139 ms 46992 KB Output is correct
20 Correct 2935 ms 46340 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 256 KB Output is correct
2 Correct 4 ms 732 KB Output is correct
3 Correct 4 ms 760 KB Output is correct
4 Correct 2 ms 380 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 8742 ms 60180 KB Output is correct
13 Correct 12058 ms 60116 KB Output is correct
14 Correct 3359 ms 58940 KB Output is correct
15 Correct 3323 ms 55132 KB Output is correct
16 Correct 2297 ms 30480 KB Output is correct
17 Correct 3500 ms 56668 KB Output is correct
18 Correct 3512 ms 55596 KB Output is correct
19 Correct 2460 ms 35324 KB Output is correct
20 Correct 5545 ms 16668 KB Output is correct
21 Correct 1404 ms 6212 KB Output is correct
22 Correct 7913 ms 23372 KB Output is correct
23 Correct 440 ms 45140 KB Output is correct
24 Correct 2372 ms 29712 KB Output is correct
25 Correct 3190 ms 46564 KB Output is correct
26 Correct 3250 ms 46856 KB Output is correct
27 Correct 2874 ms 46368 KB Output is correct
28 Execution timed out 13041 ms 185004 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 380 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 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 372 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 8770 ms 60228 KB Output is correct
13 Correct 12213 ms 60164 KB Output is correct
14 Correct 3336 ms 58840 KB Output is correct
15 Correct 3331 ms 55236 KB Output is correct
16 Correct 2373 ms 30588 KB Output is correct
17 Correct 3640 ms 56428 KB Output is correct
18 Correct 3437 ms 55456 KB Output is correct
19 Correct 2457 ms 35136 KB Output is correct
20 Correct 5511 ms 16648 KB Output is correct
21 Correct 1392 ms 6080 KB Output is correct
22 Correct 7897 ms 23348 KB Output is correct
23 Correct 451 ms 45120 KB Output is correct
24 Correct 2384 ms 29724 KB Output is correct
25 Correct 3296 ms 46448 KB Output is correct
26 Correct 3011 ms 46776 KB Output is correct
27 Correct 2810 ms 46212 KB Output is correct
28 Execution timed out 13103 ms 184872 KB Time limit exceeded
29 Halted 0 ms 0 KB -