oj.uz

Submission #153593

# Submission time Handle Problem Language Result Execution time Memory
153593 2019-09-14T19:22:38 Z youssefbou62 Game (IOI13_game) C++14
63 / 100
 13000 ms 200020 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; 
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 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 476 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 256 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 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 376 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 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 3137 ms 24856 KB Output is correct
5 Correct 2898 ms 24700 KB Output is correct
6 Correct 2279 ms 22392 KB Output is correct
7 Correct 2657 ms 21780 KB Output is correct
8 Correct 1490 ms 15648 KB Output is correct
9 Correct 2542 ms 22100 KB Output is correct
10 Correct 2524 ms 21456 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 6 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 256 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 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 6072 ms 24340 KB Output is correct
13 Correct 8036 ms 12404 KB Output is correct
14 Correct 2642 ms 5592 KB Output is correct
15 Correct 10107 ms 16200 KB Output is correct
16 Correct 938 ms 29316 KB Output is correct
17 Correct 4775 ms 20632 KB Output is correct
18 Correct 7307 ms 30800 KB Output is correct
19 Correct 6632 ms 31048 KB Output is correct
20 Correct 6513 ms 30408 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 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 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3216 ms 25160 KB Output is correct
13 Correct 2911 ms 24836 KB Output is correct
14 Correct 2439 ms 22564 KB Output is correct
15 Correct 2796 ms 22392 KB Output is correct
16 Correct 1563 ms 15760 KB Output is correct
17 Correct 2714 ms 22348 KB Output is correct
18 Correct 2537 ms 21996 KB Output is correct
19 Correct 6093 ms 24436 KB Output is correct
20 Correct 8000 ms 12380 KB Output is correct
21 Correct 2649 ms 5832 KB Output is correct
22 Correct 10161 ms 16464 KB Output is correct
23 Correct 920 ms 29296 KB Output is correct
24 Correct 4969 ms 20460 KB Output is correct
25 Correct 7407 ms 30964 KB Output is correct
26 Correct 7141 ms 30944 KB Output is correct
27 Correct 6636 ms 30516 KB Output is correct
28 Execution timed out 13111 ms 196288 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 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 476 KB Output is correct
4 Correct 2 ms 376 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 256 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 3140 ms 24852 KB Output is correct
13 Correct 2900 ms 24848 KB Output is correct
14 Correct 2365 ms 22412 KB Output is correct
15 Correct 2707 ms 22284 KB Output is correct
16 Correct 1702 ms 15680 KB Output is correct
17 Correct 2661 ms 22472 KB Output is correct
18 Correct 2738 ms 21968 KB Output is correct
19 Correct 6191 ms 24456 KB Output is correct
20 Correct 8016 ms 12384 KB Output is correct
21 Correct 2629 ms 5916 KB Output is correct
22 Correct 10276 ms 16252 KB Output is correct
23 Correct 955 ms 29376 KB Output is correct
24 Correct 4803 ms 20692 KB Output is correct
25 Correct 7372 ms 30856 KB Output is correct
26 Correct 6857 ms 31136 KB Output is correct
27 Correct 6730 ms 30296 KB Output is correct
28 Execution timed out 13099 ms 200020 KB Time limit exceeded
29 Halted 0 ms 0 KB -