oj.uz

Submission #153491

# Submission time Handle Problem Language Result Execution time Memory
153491 2019-09-14T11:00:58 Z youssefbou62 Game (IOI13_game) C++14
37 / 100
 13000 ms 65736 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std; 
using ll = long long ; 


const int N = 1e5+5 ; 
ll Mat[15][N] ; // ,st[15][4*N];
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 Update(int Row , int Ind , int L , int R  ,int node,ll val){
	// cout << "Update " << L<<" " << R << "node " << node <<endl; 
	if( L > R )return ; 
	if( L == R ){
		st[Row][node]=val; 
		return ; 
	}
	int mid = (L+R)/2 ; 
	if( Ind <= mid )
	Update(Row,Ind,L,mid,l(node),val);
	else Update(Row,Ind,mid+1,R,r(node),val); 
	st[Row][node] = gcd2(st[Row][l(node)],st[Row][r(node)]); 	
}

ll query(int Row , int QL , int QR ,int L , int R, int node ){
	// cout << "QUERY "<< L << " " << R << " node " << node << endl; 
	if( L > R || QL > R || QR < L )return 0; 
	if( L >= QL && R <= QR){
		return st[Row][node]; 
	}
	int mid = (L+R)/2 ;
	return gcd2(query(Row,QL,QR,L,mid,l(node)),query(Row,QL,QR,mid+1,R,r(node))); 
}
void init(int R, int C) {
    ROW = R; 
    COL = C; 
}

void update(int P, int Q, long long K) {
    /* ... */
    Update(P,Q,0,COL-1,0,K); 
}

long long calculate(int P, int Q, int U, int V) {
    /* ... */
	ll ans = 0 ; 
	// cerr << "query*******"<<endl; 
	for(int i = P ; i <= U  ; i++ ){
		ll q = query(i,Q,V,0,COL-1,0); 
		// cout << "i " << i << "q "<<q<<endl; 
		ans = gcd2(q,ans); 
	}
    return ans;
}
// 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 ; 
// 			update(P,Q,K);
// 		}else {
// 			int P,Q,U,V; 
// 			cin >> P >> Q >> U >> V; 
// 			cout << calculate(P,Q,U,V)<< " "; 
// 		}
// 	}
// }

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 3 ms 256 KB Output is correct
2 Correct 5 ms 740 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 4 ms 632 KB Output is correct
6 Correct 2 ms 376 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 476 KB Output is correct
10 Correct 4 ms 632 KB Output is correct
11 Correct 1 ms 380 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 360 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 5070 ms 21508 KB Output is correct
5 Correct 2337 ms 14508 KB Output is correct
6 Correct 4170 ms 63944 KB Output is correct
7 Correct 4546 ms 63784 KB Output is correct
8 Correct 3701 ms 65536 KB Output is correct
9 Correct 4566 ms 64880 KB Output is correct
10 Correct 4348 ms 63440 KB Output is correct
11 Correct 2 ms 256 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 4 ms 616 KB Output is correct
6 Correct 2 ms 376 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 376 KB Output is correct
10 Correct 4 ms 608 KB Output is correct
11 Correct 3 ms 296 KB Output is correct
12 Execution timed out 13006 ms 6692 KB Time limit exceeded
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 740 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 2 ms 400 KB Output is correct
5 Correct 4 ms 632 KB Output is correct
6 Correct 3 ms 376 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 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 5007 ms 21580 KB Output is correct
13 Correct 2331 ms 14536 KB Output is correct
14 Correct 4916 ms 63904 KB Output is correct
15 Correct 4698 ms 63536 KB Output is correct
16 Correct 3643 ms 65612 KB Output is correct
17 Correct 4355 ms 64768 KB Output is correct
18 Correct 4035 ms 63256 KB Output is correct
19 Execution timed out 13011 ms 6652 KB Time limit exceeded
20 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 5 ms 760 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 4 ms 636 KB Output is correct
6 Correct 2 ms 376 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 376 KB Output is correct
10 Correct 5 ms 620 KB Output is correct
11 Correct 4 ms 376 KB Output is correct
12 Correct 4979 ms 21512 KB Output is correct
13 Correct 2324 ms 14688 KB Output is correct
14 Correct 4568 ms 63864 KB Output is correct
15 Correct 4581 ms 63636 KB Output is correct
16 Correct 3708 ms 65736 KB Output is correct
17 Correct 4390 ms 64728 KB Output is correct
18 Correct 4208 ms 63420 KB Output is correct
19 Execution timed out 13058 ms 6556 KB Time limit exceeded
20 Halted 0 ms 0 KB -