oj.uz

Submission #153605

# Submission time Handle Problem Language Result Execution time Memory
153605 2019-09-14T20:08:06 Z youssefbou62 Game (IOI13_game) C++14
63 / 100
 5307 ms 256004 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 ; 

struct chash {
    const int RANDOM = (long long)(make_unique<char>().get()) ^ chrono::high_resolution_clock::now().time_since_epoch().count();
    static unsigned long long hash_f(unsigned long long x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    static unsigned hash_combine(unsigned a, unsigned b) { return a * 31 + b; }
    int operator()(int x) const { return hash_f(x)^RANDOM; }
};
const int N = 2005; 
gp_hash_table<int,gp_hash_table<int,ll,chash>,chash>  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));
			// if( g )
			// st[nodeC][u] = g;  		
		}
		// 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 376 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 4 ms 760 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 760 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 508 KB Output is correct
12 Correct 2 ms 252 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 376 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1878 ms 61584 KB Output is correct
5 Correct 1764 ms 61500 KB Output is correct
6 Correct 1933 ms 60296 KB Output is correct
7 Correct 2058 ms 56624 KB Output is correct
8 Correct 1371 ms 31232 KB Output is correct
9 Correct 1967 ms 58224 KB Output is correct
10 Correct 1811 ms 57112 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 4 ms 760 KB Output is correct
3 Correct 4 ms 760 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 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 4 ms 760 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 2976 ms 35120 KB Output is correct
13 Correct 4245 ms 16820 KB Output is correct
14 Correct 1516 ms 6196 KB Output is correct
15 Correct 5244 ms 23316 KB Output is correct
16 Correct 537 ms 45160 KB Output is correct
17 Correct 3143 ms 29888 KB Output is correct
18 Correct 4238 ms 46760 KB Output is correct
19 Correct 3970 ms 46804 KB Output is correct
20 Correct 4123 ms 46456 KB Output is correct
21 Correct 3 ms 376 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 5 ms 732 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 632 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 760 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 1962 ms 61756 KB Output is correct
13 Correct 1714 ms 61688 KB Output is correct
14 Correct 1835 ms 60240 KB Output is correct
15 Correct 1952 ms 56668 KB Output is correct
16 Correct 1255 ms 31168 KB Output is correct
17 Correct 2083 ms 58084 KB Output is correct
18 Correct 1900 ms 57020 KB Output is correct
19 Correct 3051 ms 35032 KB Output is correct
20 Correct 4309 ms 16728 KB Output is correct
21 Correct 1509 ms 6124 KB Output is correct
22 Correct 5221 ms 23380 KB Output is correct
23 Correct 529 ms 45124 KB Output is correct
24 Correct 2718 ms 29748 KB Output is correct
25 Correct 4216 ms 46716 KB Output is correct
26 Correct 3900 ms 46888 KB Output is correct
27 Correct 3568 ms 46468 KB Output is correct
28 Runtime error 5188 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 252 KB Output is correct
2 Correct 5 ms 716 KB Output is correct
3 Correct 4 ms 760 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 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 4 ms 760 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 1926 ms 61848 KB Output is correct
13 Correct 1755 ms 61632 KB Output is correct
14 Correct 1869 ms 60356 KB Output is correct
15 Correct 2054 ms 56656 KB Output is correct
16 Correct 1274 ms 31060 KB Output is correct
17 Correct 1986 ms 58112 KB Output is correct
18 Correct 2135 ms 57052 KB Output is correct
19 Correct 3047 ms 35220 KB Output is correct
20 Correct 4264 ms 16752 KB Output is correct
21 Correct 1492 ms 6012 KB Output is correct
22 Correct 5307 ms 23284 KB Output is correct
23 Correct 756 ms 45056 KB Output is correct
24 Correct 2889 ms 30016 KB Output is correct
25 Correct 4245 ms 46544 KB Output is correct
26 Correct 3706 ms 46952 KB Output is correct
27 Correct 3653 ms 46472 KB Output is correct
28 Runtime error 5113 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -