oj.uz

Submission #153579

# Submission time Handle Problem Language Result Execution time Memory
153579 2019-09-14T17:23:52 Z youssefbou62 Game (IOI13_game) C++14
10 / 100
 5 ms 1276 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std; 
using ll = long long ; 


const int N = 2005; 
ll  st[N][N]; 
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 4 ms 1272 KB Output is correct
3 Correct 4 ms 1276 KB Output is correct
4 Correct 2 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 3 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 888 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 Runtime error 4 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 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 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 4 ms 1276 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 1148 KB Output is correct
10 Correct 3 ms 888 KB Output is correct
11 Correct 3 ms 888 KB Output is correct
12 Runtime error 5 ms 1016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 1272 KB Output is correct
3 Correct 4 ms 1172 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 256 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 3 ms 1144 KB Output is correct
10 Correct 3 ms 888 KB Output is correct
11 Correct 4 ms 760 KB Output is correct
12 Runtime error 5 ms 376 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 252 KB Output is correct
2 Correct 4 ms 1276 KB Output is correct
3 Correct 4 ms 1244 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 292 KB Output is correct
6 Correct 4 ms 1272 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 1168 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 5 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -