Submission #578440

Source Code Expand

#include <stdio.h>
#include <stdlib.h>
typedef long int li;
typedef long long int lli;
typedef struct Node Node;

struct Node{
	Node* Left;
	Node* Parent;
	Node* Right;
	lli first;
	lli second;
	char Color;
	char Isnil;
};

enum NodeColor{Red, Black};
enum RightLeft{Right, Left};

Node root = {&root,&root,&root,0,0,1,1};
li node_num = 0;

Node* make_node(lli f,lli s){
	Node* n = (Node*)malloc(sizeof(Node));
	if(n == NULL)
		exit(EXIT_FAILURE);
	n->first = f;
	n->second = s;
	n->Left = &root;
	n->Parent = &root;
	n->Right = &root;
	n->Color = Red;
	n->Isnil = 0;
	return n;
}

void delete_node(Node* node){
	free(node);
}

void SwapColor(Node *a, Node *b){
	char c = a->Color;
	a->Color = b->Color;
	b->Color = c;
}

Node* MaxNode(Node* node){
	Node *p = node;
	while(!p->Right->Isnil)
		p = p->Right;
	return p;
}

Node* MinNode(Node* node){
	Node *p = node;
	while(!p->Left->Isnil)
		p = p->Left;
	return p;
}

Node* NextNode(Node* node){
	Node *p = node;
	if(p->Isnil)
		;
	else if(!p->Right->Isnil)
		p = MinNode(p->Right);
	else{
		while(!p->Parent->Isnil && p == p->Parent->Right)
			p = p->Parent;
		p = p->Parent;
	}

	return p;
}

Node* PrevNode(Node* node){
	Node *p = node;
	if(p->Isnil)
		p = p->Right;
	else if(!p->Left->Isnil)
		p = MaxNode(p->Left);
	else{
		while(!p->Parent->Isnil && p == p->Parent->Left)
			p = p->Parent;
		if(!p->Isnil)
			p = p->Parent;
	}

	return p;
}

void Lrotate(Node* node){
	Node *pnode = node->Right;
	node->Right = pnode->Left;

	if(!pnode->Left->Isnil)
		pnode->Left->Parent = node;

	pnode->Parent = node->Parent;

	if(node == root.Parent)
		root.Parent = pnode;
	else if(node == node->Parent->Left)
		node->Parent->Left = pnode;
	else
		node->Parent->Right = pnode;

	pnode->Left = node;
	node->Parent = pnode;
}

void Rrotate(Node* node){
	Node *pnode = node->Left;
	node->Left = pnode->Right;

	if(!pnode->Right->Isnil)
		pnode->Right->Parent = node;

	pnode->Parent = node->Parent;

	if(node == root.Parent)
		root.Parent = pnode;
	else if(node == node->Parent->Right)
		node->Parent->Right = pnode;
	else
		node->Parent->Left = pnode;

	pnode->Right = node;
	node->Parent = pnode;
}

Node* erase(Node* node){
	Node *wnode,*enode,*fnode,*fpnode,*pnode;
	if(node->Isnil)
		return &root;

	enode = pnode = node;
	wnode = NextNode(node);

	if(pnode->Left->Isnil)
		fnode = pnode->Right;
	else if(pnode->Right->Isnil)
		fnode = pnode->Left;
	else{
		pnode = wnode;
		fnode = pnode->Right;
	}

	if(pnode == enode){
		fpnode = enode->Parent;
		if(!fnode->Isnil)
			fnode->Parent = fpnode;

		if(root.Parent == enode)
			root.Parent =fnode;
		else if(fpnode->Left == enode)
			fpnode->Left = fnode;
		else
			fpnode->Right = fnode;

		if(root.Left == enode)
			root.Left = fnode->Isnil ? fpnode : MinNode(fnode);

		if(root.Right == enode)
			root.Right = fnode->Isnil ? fpnode : MaxNode(fnode);
	}else{
		enode->Left->Parent = pnode;
		pnode->Left = enode->Left;

		if(pnode == enode->Right)
			fpnode = pnode;
		else{
			fpnode = pnode->Parent;
			if(!fnode->Isnil)
				fnode->Parent = fpnode;
			fpnode->Left = fnode;
			pnode->Right = enode->Right;
			enode->Right->Parent = pnode;
		}

		if(root.Parent == enode)
			root.Parent = pnode;
		else if(enode->Parent->Left == enode)
			enode->Parent->Left = pnode;
		else
			enode->Parent->Right = pnode;

		pnode->Parent = enode->Parent;
		SwapColor(pnode,enode);
	}

	if(enode->Color == Black){
		for(;fnode!=root.Parent&&fnode->Color==Black;fpnode=fnode->Parent){
			if(fnode == fpnode->Left){
				pnode = fpnode->Right;
				if(pnode->Color == Red){
					pnode->Color = Black;
					fpnode->Color = Red;
					Lrotate(fpnode);
					pnode = fpnode->Right;
				}

				if(pnode->Isnil)
					fnode = fpnode;
				else if(pnode->Left->Color==Black&&pnode->Right->Color==Black){
					pnode->Color = Red;
					fnode = fpnode;
				}else{
					if(pnode->Right->Color == Black){
						pnode->Left->Color = Black;
						pnode->Color = Red;
						Rrotate(pnode);
						pnode = fpnode->Right;
					}

					pnode->Color = fpnode->Color;
					fpnode->Color = Black;
					pnode->Right->Color = Black;
					Lrotate(fpnode);
					break;
				}
			}else{
				pnode = fpnode->Left;
				if(pnode->Color == Red){
					pnode->Color = Black;
					fpnode->Color = Red;
					Rrotate(fpnode);
					pnode = fpnode->Left;
				}
				if(pnode->Isnil)
					fnode = fpnode;
				else if(pnode->Right->Color==Black&& pnode->Left->Color==Black){
					pnode->Color = Red;
					fnode = fpnode;
				}else{
					if(pnode->Left->Color == Black){
						pnode->Right->Color = Black;
						pnode->Color = Red;
						Lrotate(pnode);
						pnode = fpnode->Left;
					}

					pnode->Color = fpnode->Color;
					fpnode->Color = Black;
					pnode->Left->Color = Black;
					Rrotate(fpnode);
					break;
				}
			}
			
		}
		fnode->Color = Black;
	}
	delete_node(enode);

	if(0 < node_num)
		--node_num;

	return wnode;
}

Node* InsertFunc(char left, Node* wnode, Node* node){
	Node *pnode;

	++node_num;
	node->Parent = wnode;

	if(wnode == &root)
		root.Left = root.Parent = root.Right = node;
	else if(left){
		wnode->Left = node;
		if(wnode == root.Left)
			root.Left = node;
	}else{
		wnode->Right = node;
		if(wnode == root.Right)
			root.Right = node;
	}

	for(pnode = node;pnode->Parent->Color == Red;){
		if(pnode->Parent == pnode->Parent->Parent->Left){
			wnode = pnode->Parent->Parent->Right;
			if(wnode->Color == Red){
				pnode->Parent->Color = Black;
				wnode->Color = Black;
				pnode->Parent->Parent->Color = Red;
				pnode = pnode->Parent->Parent;
			}else{
				if(pnode == pnode->Parent->Right){
					pnode = pnode->Parent;
					Lrotate(pnode);
				}
				pnode->Parent->Color = Black;
				pnode->Parent->Parent->Color = Red;
				Rrotate(pnode->Parent->Parent);
			}
		}else{
			wnode = pnode->Parent->Parent->Left;
			if(wnode->Color == Red){
				pnode->Parent->Color = Black;
				wnode->Color = Black;
				pnode->Parent->Parent->Color = Red;
				pnode = pnode->Parent->Parent;
			}else{
				if(pnode == pnode->Parent->Left){
					pnode = pnode->Parent;
					Rrotate(pnode);
				}
				pnode->Parent->Color = Black;
				pnode->Parent->Parent->Color = Red;
				Lrotate(pnode->Parent->Parent);
			}
		}
	}
	root.Parent->Color = Black;

	return node;
}

Node* insert(Node* node){
	char Addleft = Left;
	Node *tnode,*wnode,*pnode;

	tnode = root.Parent;
	wnode = &root;

	while(!tnode->Isnil){
		wnode = tnode;
		if(node->first < tnode->first){
			tnode = tnode->Left;
			Addleft = Left;
		}else{
			tnode = tnode->Right;
			Addleft = Right;
		}
	}

	pnode = wnode;
	if(!Addleft)
		;
	else if(pnode == root.Left)
		return InsertFunc(Left,wnode,node);
	else
		pnode = PrevNode(wnode);

	if(pnode->first < node->first)
		return InsertFunc(Addleft,wnode,node);

	return 0;
}

Node* lower_bound(lli key){
	Node *pnode,*wnode;

	pnode = root.Parent;
	wnode = &root;

	while(!pnode->Isnil){
		if(pnode->first < key)
			pnode = pnode->Right;
		else{
			wnode = pnode;
			pnode = pnode->Left;
		}
	}
	return wnode;
}

int main(){
	Node *node,*bnode;
	li n,i;
	lli s,c,f,d;

	scanf("%ld",&n);
	for(i=0;i<n;i++){
		scanf("%lld %lld",&s,&c);
		node = lower_bound(s);
		f = s;
		if(node != root.Left){
			bnode = PrevNode(node);
			if(s-1 <= bnode->second){
				f = bnode->first;
				s = bnode->second + 1;
				erase(bnode);
			}
		}
		while(!node->Isnil){
			d = node->first - s;
			if(c > d){
				c -= d;
				s = node->second + 1;
				bnode = node;
				node = NextNode(node);
				erase(bnode);
			}else{
				s += c - 1;
				c = 0;
				break;
			}
		}
		if(c > 0)
			s += c - 1;
		printf("%lld\n",s);

		if(!node->Isnil && s + 1 == node->first){
			s = node->second;
			erase(node);
		}

		insert(make_node(f,s));
	}

	return 0;
}

Submission Info

Submission Time
Task D - Squares, Pieces and Coloring
User niconico774
Language C (GCC 4.9.2)
Score 100
Code Size 8097 Byte
Status AC
Exec Time 166 ms
Memory 6900 KiB

Compile Error

./Main.c: In function ‘main’:
./Main.c:374:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%ld",&n);
  ^
./Main.c:376:3: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&s,&c);
   ^

Judge Result

Set Name Sample Dataset1 Dataset2 Dataset3
Score / Max Score 0 / 0 35 / 35 40 / 40 25 / 25
Status
AC × 3
AC × 11
AC × 15
AC × 36
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt
Dataset1 sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt
Dataset2 sample-01.txt, sample-02.txt, sample-03.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt
Dataset3 sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 03-06.txt, 03-07.txt, 03-08.txt, 03-09.txt, 03-10.txt, 03-11.txt, 03-12.txt
Case Name Status Exec Time Memory
01-01.txt AC 55 ms 796 KiB
01-02.txt AC 84 ms 788 KiB
01-03.txt AC 107 ms 1320 KiB
01-04.txt AC 85 ms 3828 KiB
01-05.txt AC 24 ms 696 KiB
01-06.txt AC 22 ms 792 KiB
01-07.txt AC 24 ms 792 KiB
01-08.txt AC 30 ms 800 KiB
01-09.txt AC 87 ms 1500 KiB
02-01.txt AC 25 ms 792 KiB
02-02.txt AC 26 ms 672 KiB
02-03.txt AC 24 ms 800 KiB
02-04.txt AC 26 ms 628 KiB
02-05.txt AC 25 ms 792 KiB
02-06.txt AC 25 ms 700 KiB
02-07.txt AC 24 ms 708 KiB
02-08.txt AC 24 ms 792 KiB
02-09.txt AC 25 ms 796 KiB
02-10.txt AC 23 ms 788 KiB
02-11.txt AC 24 ms 700 KiB
02-12.txt AC 23 ms 672 KiB
03-01.txt AC 133 ms 700 KiB
03-02.txt AC 132 ms 788 KiB
03-03.txt AC 123 ms 672 KiB
03-04.txt AC 86 ms 792 KiB
03-05.txt AC 156 ms 6896 KiB
03-06.txt AC 120 ms 796 KiB
03-07.txt AC 130 ms 796 KiB
03-08.txt AC 166 ms 6900 KiB
03-09.txt AC 166 ms 6880 KiB
03-10.txt AC 36 ms 800 KiB
03-11.txt AC 127 ms 796 KiB
03-12.txt AC 127 ms 676 KiB
sample-01.txt AC 24 ms 800 KiB
sample-02.txt AC 23 ms 796 KiB
sample-03.txt AC 24 ms 796 KiB