oj.uz

Submission #153734

# Submission time Handle Problem Language Result Execution time Memory
153734 2019-09-15T14:46:44 Z youssefbou62 Game (IOI13_game) C++14
37 / 100
 13000 ms 30028 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; 
unordered_map<int,unordered_map<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));
		}
		// 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); 
	ll g=gcd2(get(nodeC,l(u)),get(nodeC,r(u))); 
	if( g )
	st[nodeC][u] = g ; 
}
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(){
// 	// cout << (sizeof (st)) << endl; 
// 	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; 
// 		}
// 	}
// 	// cout << (sizeof (st)) << 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 6 ms 504 KB Output is correct
3 Correct 6 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 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 4 ms 376 KB Output is correct
11 Correct 4 ms 376 KB Output is correct
12 Correct 2 ms 376 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 3 ms 400 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 4247 ms 29836 KB Output is correct
5 Correct 4021 ms 29748 KB Output is correct
6 Correct 3180 ms 27444 KB Output is correct
7 Correct 3750 ms 27100 KB Output is correct
8 Correct 2024 ms 18420 KB Output is correct
9 Correct 3488 ms 27344 KB Output is correct
10 Correct 3563 ms 27052 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 6 ms 508 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 6 ms 504 KB Output is correct
10 Correct 4 ms 376 KB Output is correct
11 Correct 4 ms 376 KB Output is correct
12 Correct 9598 ms 29184 KB Output is correct
13 Correct 11945 ms 14100 KB Output is correct
14 Correct 3252 ms 3904 KB Output is correct
15 Execution timed out 13087 ms 18168 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 6 ms 548 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 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 4 ms 376 KB Output is correct
12 Correct 4434 ms 28348 KB Output is correct
13 Correct 3956 ms 29228 KB Output is correct
14 Correct 3219 ms 25704 KB Output is correct
15 Correct 4049 ms 25900 KB Output is correct
16 Correct 2237 ms 17904 KB Output is correct
17 Correct 3653 ms 26136 KB Output is correct
18 Correct 3505 ms 25432 KB Output is correct
19 Correct 9483 ms 30028 KB Output is correct
20 Correct 11204 ms 14824 KB Output is correct
21 Correct 3240 ms 4624 KB Output is correct
22 Execution timed out 13095 ms 18956 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0 / 20.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 6 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 6 ms 504 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 252 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 4 ms 376 KB Output is correct
11 Correct 4 ms 376 KB Output is correct
12 Correct 4334 ms 29088 KB Output is correct
13 Correct 3965 ms 29084 KB Output is correct
14 Correct 3129 ms 26272 KB Output is correct
15 Correct 3859 ms 25908 KB Output is correct
16 Correct 2186 ms 17704 KB Output is correct
17 Correct 3472 ms 26120 KB Output is correct
18 Correct 3630 ms 25476 KB Output is correct
19 Correct 9580 ms 29400 KB Output is correct
20 Correct 12244 ms 14376 KB Output is correct
21 Correct 3222 ms 4628 KB Output is correct
22 Execution timed out 13089 ms 18768 KB Time limit exceeded
23 Halted 0 ms 0 KB -