oj.uz

Submission #153588

# Submission time Handle Problem Language Result Execution time Memory
153588 2019-09-14T18:58:39 Z youssefbou62 Game (IOI13_game) C++14
63 / 100
 9519 ms 256004 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std; 
using ll = long long ; 


const int N = 2005; 
unordered_map<int,unordered_map<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 ; 
}
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(st[l(nodeC)][(u)],st[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(st[nodeC][l(u)],st[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 st[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 380 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 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 376 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 3 ms 424 KB Output is correct
12 Correct 2 ms 360 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 2804 ms 43368 KB Output is correct
5 Correct 2041 ms 37804 KB Output is correct
6 Correct 3434 ms 91280 KB Output is correct
7 Correct 3626 ms 91052 KB Output is correct
8 Correct 3165 ms 88640 KB Output is correct
9 Correct 3782 ms 92780 KB Output is correct
10 Correct 3258 ms 90692 KB Output is correct
11 Correct 3 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 604 KB Output is correct
3 Correct 3 ms 632 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 652 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 4 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 4266 ms 36024 KB Output is correct
13 Correct 5379 ms 16872 KB Output is correct
14 Correct 2568 ms 7016 KB Output is correct
15 Correct 7110 ms 24060 KB Output is correct
16 Correct 932 ms 47540 KB Output is correct
17 Correct 7859 ms 175120 KB Output is correct
18 Correct 9356 ms 189532 KB Output is correct
19 Correct 8990 ms 189448 KB Output is correct
20 Correct 9030 ms 188436 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 376 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 5 ms 632 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 632 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 3 ms 396 KB Output is correct
12 Correct 2892 ms 43240 KB Output is correct
13 Correct 2041 ms 37856 KB Output is correct
14 Correct 3702 ms 91196 KB Output is correct
15 Correct 3545 ms 90880 KB Output is correct
16 Correct 2929 ms 88580 KB Output is correct
17 Correct 3536 ms 92840 KB Output is correct
18 Correct 3410 ms 90744 KB Output is correct
19 Correct 4207 ms 36080 KB Output is correct
20 Correct 5383 ms 17012 KB Output is correct
21 Correct 2539 ms 7136 KB Output is correct
22 Correct 7109 ms 24136 KB Output is correct
23 Correct 893 ms 47672 KB Output is correct
24 Correct 8175 ms 175292 KB Output is correct
25 Correct 9519 ms 189608 KB Output is correct
26 Correct 8919 ms 189536 KB Output is correct
27 Correct 8709 ms 188484 KB Output is correct
28 Runtime error 1725 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 256 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 380 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 2 ms 276 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 380 KB Output is correct
12 Correct 2727 ms 43108 KB Output is correct
13 Correct 2067 ms 38072 KB Output is correct
14 Correct 4058 ms 91096 KB Output is correct
15 Correct 3529 ms 90820 KB Output is correct
16 Correct 2963 ms 88640 KB Output is correct
17 Correct 3426 ms 92796 KB Output is correct
18 Correct 3383 ms 90828 KB Output is correct
19 Correct 4196 ms 35996 KB Output is correct
20 Correct 5486 ms 16992 KB Output is correct
21 Correct 2613 ms 7152 KB Output is correct
22 Correct 7219 ms 24184 KB Output is correct
23 Correct 914 ms 47648 KB Output is correct
24 Correct 8151 ms 175172 KB Output is correct
25 Correct 9134 ms 189488 KB Output is correct
26 Correct 9069 ms 189324 KB Output is correct
27 Correct 9127 ms 188444 KB Output is correct
28 Runtime error 1887 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -