Submission #123838

#	Time	Username	Problem	Language	Result	Execution time	Memory
123838		MAMBA	Game (IOI13_game)	C++17	0 / 100	3 ms	504 KiB

game

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

using namespace std;

typedef long long ll;

struct node2 {
	node2* L = NULL;
	node2* R = NULL;
	int l = -1, r = -1;
	ll g = 0;
	node2(int l_ = 0, int r_ = 1e9 + 5) {
		l = l_, r = r_;
	}
};

struct node {
	node * L = NULL;
	node* R = NULL;
	int l = -1, r = -1;
	node2 * ptr = NULL;
	node(int l_  = 0, int r_ = 1e9 + 5) {
		l = l_, r = r_;
	}
};

node* root = NULL;


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;
}

void segUpd(node2 * me, int t, ll k) {
	if (me->l == me->r - 1) {
		me->g = k;
		return;
	}
	int mid = me->l + me->r >> 1;
	if (t < mid) {
		if (me->L == NULL)
			me->L = new node2(me->l , mid);
		segUpd(me->L , t , k);
	}
	else {
		if (me->R == NULL)
			me->R = new node2(mid , me->r);
		segUpd(me->R , t , k);
	}
	ll l = 0, r = 0;
	if (me->L != NULL) l = me->L->g;
	if (me->R != NULL) r = me->R->g;
	me->g = gcd2(l , r);
}

void segUpd(node * me , int s , int t, ll k) {
	if (me->l == me->r - 1) {
		if (me->ptr == NULL)
			me->ptr = new node2();
		segUpd(me->ptr , t , k);
		return;
	}
	int mid = me->l + me->r >> 1;
	if (s < mid) {
		if (me->L == NULL)
			me->L = new node(me->l , mid);
		segUpd(me->L , s , t , k);
	}
	else {
		if (me->R == NULL)
			me->R = new node(mid , me->r);
		segUpd(me->R , s , t , k);
	}
}

ll segGet(node2 *me , int s, int t) {
	if (me->l  >= s && me->r <= t) {
		return me->g;
	}
	int mid = me->l + me->r >> 1;
	ll l = 0;
	if (s < mid && me->L != NULL)
		l = segGet(me->L , s , t);

	ll r = 0;
	if (t > mid && me->R != NULL)
		r = segGet(me->R , s , t);
	return gcd2(l , r);
}


ll segGet(node *me , int s, int t, int s2, int t2) {
	if (me->l  >= s && me->r <= t) {
		if (me->ptr == NULL)
			return 0;
		return segGet(me->ptr , s2 , t2);		
	}
	int mid = me->l + me->r >> 1;
	ll l = 0;
	if (s < mid && me->L != NULL)
		l = segGet(me->L , s , t , s2 , t2);

	ll r = 0;
	if (t > mid && me->R != NULL)
		r = segGet(me->R , s , t , s2 , t2);
	return gcd2(l , r);
}

void init(int R, int C) {
   	root = new node();
}

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

long long calculate(int P, int Q, int U, int V) {
    return segGet(root , P , U + 1 , Q , V + 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;
      ^~~
game.cpp: In function 'void segUpd(node2*, int, ll)':
game.cpp:46:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = me->l + me->r >> 1;
            ~~~~~~^~~~~~~
game.cpp: In function 'void segUpd(node*, int, int, ll)':
game.cpp:70:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = me->l + me->r >> 1;
            ~~~~~~^~~~~~~
game.cpp: In function 'll segGet(node2*, int, int)':
game.cpp:87:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = me->l + me->r >> 1;
            ~~~~~~^~~~~~~
game.cpp: In function 'll segGet(node*, int, int, int, int)':
game.cpp:105:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = me->l + me->r >> 1;
            ~~~~~~^~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20