oj.uz

Submission #123865

# Submission time Handle Problem Language Result Execution time Memory
123865 2019-07-02T08:14:30 Z MAMBA Game (IOI13_game) C++17
0 / 100
 1284 ms 73440 KB 
#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->ptr == NULL)
		me->ptr = new node2();
	segUpd(me->ptr , t , k);

	if (me->l == me->r - 1) {
		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->ptr == NULL) return 0;
	if (me->l >= s && me->r <= t) {
		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

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:71: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:88: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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Incorrect 5 ms 888 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 1284 ms 73380 KB Output is correct
5 Incorrect 926 ms 73440 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 5 ms 892 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Incorrect 6 ms 888 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 8 ms 888 KB Output isn't correct
3 Halted 0 ms 0 KB -