oj.uz

Submission #153494

# Submission time Handle Problem Language Result Execution time Memory
153494 2019-09-14T11:04:23 Z youssefbou62 Game (IOI13_game) C++14
37 / 100
 13000 ms 63188 KB 
#include <bits/stdc++.h>
#include "game.h"
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
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 2 ms 256 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 5 ms 636 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 4 ms 636 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 504 KB Output is correct
10 Correct 4 ms 632 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 348 KB Output is correct
4 Correct 4577 ms 17396 KB Output is correct
5 Correct 2211 ms 11516 KB Output is correct
6 Correct 3877 ms 59428 KB Output is correct
7 Correct 4669 ms 59300 KB Output is correct
8 Correct 3391 ms 62292 KB Output is correct
9 Correct 4072 ms 60400 KB Output is correct
10 Correct 3784 ms 59036 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 4 ms 632 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 4 ms 632 KB Output is correct
6 Correct 3 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 504 KB Output is correct
10 Correct 4 ms 632 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Execution timed out 13022 ms 6620 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 636 KB Output is correct
3 Correct 4 ms 636 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 3 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 504 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 4675 ms 17844 KB Output is correct
13 Correct 2234 ms 11812 KB Output is correct
14 Correct 4198 ms 59704 KB Output is correct
15 Correct 4086 ms 59592 KB Output is correct
16 Correct 3663 ms 62844 KB Output is correct
17 Correct 4018 ms 60844 KB Output is correct
18 Correct 3952 ms 59628 KB Output is correct
19 Execution timed out 13081 ms 6732 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 4 ms 632 KB Output is correct
3 Correct 4 ms 656 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 3 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 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 4598 ms 18272 KB Output is correct
13 Correct 2236 ms 12408 KB Output is correct
14 Correct 4244 ms 60232 KB Output is correct
15 Correct 4143 ms 60104 KB Output is correct
16 Correct 3426 ms 63188 KB Output is correct
17 Correct 4109 ms 61300 KB Output is correct
18 Correct 4248 ms 59952 KB Output is correct
19 Execution timed out 13053 ms 6796 KB Time limit exceeded
20 Halted 0 ms 0 KB -