oj.uz

Submission #349643

# Submission time Handle Problem Language Result Execution time Memory
349643 2021-01-18T05:26:14 Z tengiz05 Game (IOI13_game) C++17
0 / 100
 1 ms 492 KB 
#include "game.h"
#ifndef EVAL
#include "grader.c"
#endif
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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;
}
const int N = 4005;
ll n, m;
vector<vector<int>> t;
ll get(int x1, int y1, int x2, int y2){
	ll res = 0;
	for(x1+=n,x2+=n; x1<=x2; x1>>=1,x2>>=1){
		if(x1&1){
			for(int l=y1+m,r=y2+m; l<=r; l>>=1,r>>=1){
				if(l&1)res = gcd2(res, t[x1][l++]);
				if(!(r&1))res = gcd2(res, t[x1][r--]);
			}
			x1++;
		}if(!(x2&1)){
			for(int l=y1+m,r=y2+m; l<=r; l>>=1,r>>=1){
				if(l&1)res = gcd2(res, t[x2][l++]);
				if(!(r&1))res = gcd2(res, t[x2][r--]);
			}
			x2--;
		}
	}return res;
}

void upd(int x, int y, ll val){
	for(x+=n; x>=1; x>>=1){
		int i = y+m;
		for(; i>0; i>>=1){
			if(x>=n&&i>=m)t[x][i] = val;
			else if(i>=m)t[x][i] = gcd2(t[x<<1][i],t[x<<1|1][i]);
			t[x][i>>1] = gcd2(t[x][i], t[x][i^1]);
		}
	}
}

void init(int R, int C) {
	n = R, m = C;
	t.assign(n,vector<int>(m,0));
}

void update(int P, int Q, long long K) {
	upd(P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
	//~ cout << "the initial array is:\n";
	//~ for(int i=0;i<n;i++){
		//~ for(int j=0;j<m;j++){
			//~ cout << get(i,j,i,j) << ' ';
		//~ }cout << '\n';
	//~ }cout << '\n';
	return get(P, Q, U, V);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -