oj.uz

Submission #153580

# Submission time Handle Problem Language Result Execution time Memory
153580 2019-09-14T17:25:26 Z youssefbou62 Game (IOI13_game) C++14
36 / 100
 3321 ms 134100 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std; 
using ll = long long ; 


const int N = 2005; 
ll  st[N*4][N*4]; 
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 376 KB Output is correct
2 Correct 3 ms 1272 KB Output is correct
3 Correct 4 ms 1272 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 1272 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 1160 KB Output is correct
10 Correct 3 ms 892 KB Output is correct
11 Correct 3 ms 888 KB Output is correct
12 Correct 3 ms 376 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Runtime error 27 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 1272 KB Output is correct
3 Correct 4 ms 1272 KB Output is correct
4 Correct 2 ms 352 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 1272 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 1144 KB Output is correct
10 Correct 4 ms 888 KB Output is correct
11 Correct 3 ms 888 KB Output is correct
12 Correct 1356 ms 47708 KB Output is correct
13 Correct 2722 ms 39812 KB Output is correct
14 Correct 881 ms 8296 KB Output is correct
15 Correct 3321 ms 89832 KB Output is correct
16 Correct 363 ms 132448 KB Output is correct
17 Correct 1882 ms 113836 KB Output is correct
18 Correct 2421 ms 133628 KB Output is correct
19 Correct 2293 ms 134100 KB Output is correct
20 Correct 2126 ms 133408 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 1272 KB Output is correct
3 Correct 4 ms 1272 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 1272 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 4 ms 1272 KB Output is correct
10 Correct 3 ms 876 KB Output is correct
11 Correct 3 ms 760 KB Output is correct
12 Runtime error 27 ms 496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 4 ms 1276 KB Output is correct
3 Correct 4 ms 1272 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 1272 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 1144 KB Output is correct
10 Correct 3 ms 888 KB Output is correct
11 Correct 3 ms 760 KB Output is correct
12 Runtime error 27 ms 380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -