oj.uz

Submission #153591

# Submission time Handle Problem Language Result Execution time Memory
153591 2019-09-14T19:10:20 Z youssefbou62 Game (IOI13_game) C++14
63 / 100
 9861 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 ; 
}
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 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 256 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 2 ms 128 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 4 ms 504 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 504 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 420 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 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2694 ms 31420 KB Output is correct
5 Correct 2062 ms 24876 KB Output is correct
6 Correct 3620 ms 86584 KB Output is correct
7 Correct 3484 ms 86376 KB Output is correct
8 Correct 2957 ms 86584 KB Output is correct
9 Correct 3945 ms 88608 KB Output is correct
10 Correct 3376 ms 86128 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 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 5 ms 504 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 504 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 4 ms 376 KB Output is correct
12 Correct 4206 ms 24900 KB Output is correct
13 Correct 5529 ms 12544 KB Output is correct
14 Correct 2778 ms 7284 KB Output is correct
15 Correct 6990 ms 16296 KB Output is correct
16 Correct 924 ms 29264 KB Output is correct
17 Correct 7939 ms 170328 KB Output is correct
18 Correct 9214 ms 181248 KB Output is correct
19 Correct 9318 ms 180856 KB Output is correct
20 Correct 9128 ms 180204 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 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 5 ms 504 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 504 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2615 ms 31424 KB Output is correct
13 Correct 2069 ms 24824 KB Output is correct
14 Correct 3503 ms 86776 KB Output is correct
15 Correct 3536 ms 86340 KB Output is correct
16 Correct 2936 ms 86480 KB Output is correct
17 Correct 3814 ms 88568 KB Output is correct
18 Correct 3914 ms 86140 KB Output is correct
19 Correct 4248 ms 24916 KB Output is correct
20 Correct 5501 ms 12528 KB Output is correct
21 Correct 2756 ms 7016 KB Output is correct
22 Correct 7031 ms 16452 KB Output is correct
23 Correct 862 ms 29484 KB Output is correct
24 Correct 8084 ms 170448 KB Output is correct
25 Correct 9594 ms 181232 KB Output is correct
26 Correct 9807 ms 180856 KB Output is correct
27 Correct 8992 ms 180168 KB Output is correct
28 Runtime error 1857 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 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 5 ms 508 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2739 ms 31188 KB Output is correct
13 Correct 2170 ms 24868 KB Output is correct
14 Correct 3635 ms 86476 KB Output is correct
15 Correct 3871 ms 86244 KB Output is correct
16 Correct 2916 ms 86456 KB Output is correct
17 Correct 3803 ms 88624 KB Output is correct
18 Correct 3511 ms 86180 KB Output is correct
19 Correct 4344 ms 24972 KB Output is correct
20 Correct 5544 ms 12408 KB Output is correct
21 Correct 2721 ms 6900 KB Output is correct
22 Correct 6991 ms 16456 KB Output is correct
23 Correct 919 ms 29492 KB Output is correct
24 Correct 8224 ms 170448 KB Output is correct
25 Correct 9482 ms 181224 KB Output is correct
26 Correct 9861 ms 180928 KB Output is correct
27 Correct 9219 ms 180052 KB Output is correct
28 Runtime error 1776 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -