Submission #238488

#	Time	Username	Problem	Language	Result	Execution time	Memory
238488		figter001	Game (IOI13_game)	C++17	63 / 100	1904 ms	256004 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define fast ios::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int TO = 1e9 + 1;

int r,c,n;
int p,q;

struct node{
	node *l,*r;
	ll val;
	node(){
		l = r = NULL;
		val = 0;
	}
	void marge(){
		val = __gcd(l->val , r->val);
	}
};

struct node2d{
	node2d *l,*r;
	node *child;
	ll val;
	node2d(){
		l = r = NULL;
		val = 0;
		child = new node();
	}
	void marge(){
		val = __gcd(l->val , r->val);
	}
};

node2d *head2d;

void update_range(int at,ll val,node *&n,int s = 1,int e = c){
	if(n == NULL)n = new node();
	if(s > at || e < at)return;
	if(s == e){
		n->val = val;
		return;
	}
	update_range(at , val , n->l , s , (s+e)/2);
	update_range(at , val , n->r , (s+e)/2+1 , e);
	n->marge();
}

ll get(int l,int r,node *&n,int s = 1,int e = c){
	if(n == NULL)return 0;
	if(n->val == 0)return 0;
	if(s > r || e < l || l > r)return 0LL;
	if(s >= l && e <= r)return n->val;
	ll a = get(l , r , n->l , s , (s+e) / 2);
	ll b = get(l , r , n->r , (s+e)/2+1 , e);
	return __gcd(a,b);
}

void update_range_2(int at,node *&n,node *&l , node*&r,int s = 1,int e = c){
	if(n == NULL)n = new node();
	if(s > at || e < at)return;	
	if(s == e){
		if(l == NULL)n->val = r->val;
		else if(r == NULL)n->val = l->val;
		else n->val = __gcd(l->val,r->val);
		return;
	}
	int md = (s+e)/2;
	if(l == NULL){
		update_range_2(at , n->l,l,r->l , s , md);
		update_range_2(at , n->r,l,r->r , md+1 , e);	
	}else if(r == NULL){
		update_range_2(at , n->l,l->l,r , s , md);
		update_range_2(at , n->r,l->r,r , md+1 , e);
	}else{
		update_range_2(at , n->l,l->l,r->l , s , md);
		update_range_2(at , n->r,l->r,r->r , md+1 , e);
	}
	n->marge();
}

void update_range_2d(int at,ll val,node2d *&n = head2d,int s = 1,int e = ::r){
	if(n == NULL)n = new node2d();
	if(s > at || e < at)return;
	if(s == e){
		update_range(p,val,n->child);
		n->val = n->child->val;
		return;
	}
	update_range_2d(at , val , n->l , s , (s+e)/2);
	update_range_2d(at , val , n->r , (s+e)/2+1 , e);
	update_range_2(p,n->child,n->l->child,n->r->child);
	n->marge();
}

ll get_2d(int l,int r,node2d *& n = head2d,int s = 1,int e = ::r){
	if(n == NULL)return 0;
	if(n->val == 0)return 0;
	if(s > r || e < l || l > r)return 0;
	if(s >= l && e <= r){
		return get(p,q,n->child);
	}
	ll a = get_2d(l , r , n->l , s , (s+e) / 2);
	ll b = get_2d(l , r , n->r , (s+e)/2+1 , e);
	return __gcd(a,b);
}
 
void init(int R, int C) {
	r = R;
	c = C;
    head2d = new node2d();
}
 
void update(int P, int Q, long long K) {
	p = Q + 1;
	update_range_2d(P+1,K); 
}
 
long long calculate(int P, int Q, int U, int V) {
	p = Q + 1;q = V + 1;
	return get_2d(P+1,U+1);
}

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