Submission #153491

#	Time	Username	Problem	Language	Result	Execution time	Memory
153491		youssefbou62	Game (IOI13_game)	C++14	37 / 100	13058 ms	65736 KiB

game

#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 (stderr)

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20