Perhaps you didn't take into account the case that there are some numbers of the same value in the input.
Give you a set of data your code failed to deal with:
7 3
1 5 1 1 1 2 2
1 3 2
2 4 1
3 7 3

Correct ans:
1
1
1

Yours:
5
1
-1
( vc6.0 c++ )

Sorry your code is too long for me to read. What's more, I didn't use
class before. It makes me be afraid of your program.
:)

> I think init of answer array is not needed because it overlaped by another set of questions.
> 
> and...
> 
> this is my RB Tree. 
> but this is very long... that's reason why i didn't post it
> 
> 
> 
> #include <cstdio>
> #include <cstdlib>
> #include <queue>
> 
> #include <string>
> #include <ctime>
> #include <algorithm>
> #include <set>
> 
> using namespace std;
> 
> class Node {
> 	public:
> 		Node* left;
> 		Node* right;
> 		int red;	// 0 black 1 red
> 		int key;
> 		int treesize;
> 		Node() {
> 			left = NULL, right = NULL;
> 			red = 0;
> 			key = 0;
> 			treesize = 1;
> 		}
> 		Node(int key) {
> 			left = NULL, right = NULL;
> 			red = 0;
> 			this->key = key;
> 			treesize = 1;
> 		}
> };
> 
> class RedBlack {
> 	public:	
> 		int treesize;
> 		Node* base;
> 
> 		RedBlack() {
> 			base = new Node();
> 			treesize = 0;
> 		}
> 
> 		~RedBlack() {
> 			queue<Node*> bfs;
> 			bfs.push(base);
> 
> 			while(!bfs.empty()) {
> 				Node* now = bfs.front();
> 				bfs.pop();
> 				if (now) {
> 					bfs.push(now->left);
> 					bfs.push(now->right);
> 					delete now;
> 					now = NULL;
> 				}
> 			}
> 
> 		}
> 
> 		int size() {
> 			return treesize;
> 		}
> 
> 		//찾으면 Node* 리턴. 못찾으면 Null 리턴
> 		//base의 left가 root
> 		Node* find(int key)
> 		{
> 			Node* s = base->left;
> 			while(s != NULL && s->key != key) {
> 				if (s->key > key) {
> 					s = s->left;
> 				}
> 				else {
> 					s = s->right;
> 				}
> 			}
> 			return s;
> 		}
> 
> 		int rank(int k)
> 		{
> 			if (k < 0 || k > base->left->treesize) return -1;
> 			Node* s = base->left;
> 			int nodenum = 1;
> 			while(1)
> 			{
> 				if (s->left) nodenum += s->left->treesize;
> 
> 				if (nodenum == k) return s->key;
> 				if (k < nodenum) {
> 					nodenum -= s->left->treesize;
> 					s = s->left;
> 				}
> 				else {
> 					nodenum++;
> 					s = s->right;
> 				}
> 			}
> 			//should not reached
> 			printf("should not reached!!!!\n");
> 			(*(int *)0) = 0;
> 			return -1;
> 		}
> 
> 		//pivot의 위치는 변하지 않고, gchild가 회전된 서브트리의 root가 된다.
> 		//회전된 서브트리의 root의 Pointer가 리턴
> 		Node* rotate(Node* pivot, int key)
> 		{
> 			Node* child, *gchild;
> 			if (key < pivot->key || pivot == base) child = pivot -> left;
> 			else child = pivot -> right;
> 
> 			int save = child->treesize;
> 			if (key < child->key) {	//L 회전
> 				gchild = child->left;
> 				child->treesize -= gchild->treesize;
> 				if (gchild->right) child->treesize += gchild->right->treesize;
> 
> 				child->left = gchild->right;
> 				gchild->right = child;
> 			}
> 			else {					//R 회전
> 				gchild = child->right;
> 				child->treesize -= gchild->treesize;
> 				if (gchild->left) child->treesize += gchild->left->treesize;
> 
> 				child->right = gchild->left;
> 				gchild->left = child;
> 			}
> 			gchild->treesize = save;
> 
> 
> 			if (key < pivot->key || pivot == base) pivot->left = gchild;
> 			else pivot->right = gchild;
> 
> 			return gchild;
> 		}
> 
> 		Node* insert(int key)
> 		{
> 			Node* t, *parent, *gparent, *ggparent;
> 			ggparent = gparent = parent = base;
> 			t = base->left;
> 
> 			while(t != NULL) {
> 				if (key == t->key) return NULL;	//이미 같은 키가 존재
> 				if (t->left != NULL && t-> right != NULL && t->left->red && t->right->red) { //색상변환
> 					t->red = 1;
> 					t->left->red = 0, t->right->red = 0;
> 					if (parent->red) {	//부모가 빨강이면 회전 필요
> 						gparent->red = 1;
> 						if ((key < gparent->key) != (key < parent->key)) //LR이나 RL의 첫 회전
> 							parent = rotate(gparent, key);
> 						t = rotate(ggparent, key);
> 						t->red = 0;
> 					}
> 					base->left->red = 0;	//root는 항상 검정
> 				}
> 				ggparent = gparent;
> 				gparent = parent;
> 				parent = t;
> 				if (key < t->key) t = t->left;
> 				else t = t->right;
> 			}
> 
> 			t = new Node(key);	
> 			if (key < parent->key || parent == base) parent->left = t;
> 			else parent->right = t;
> 
> 			t->red = 1;	//새로 삽입된 노드는 빨강
> 
> 			//root에서 t의 parent까지 treesize에 1을 더한다
> 			Node* s = base->left;
> 			while(s != NULL && s->key != key) {
> 				s->treesize ++;
> 				if (s->key > key) {
> 					s = s->left;
> 				}
> 				else {
> 					s = s->right;
> 				}
> 			}
> 
> 			if (parent->red) {
> 				gparent->red = 1;
> 				if ((key < gparent->key) != (key < parent->key)) //LR이나 RL의 첫 회전
> 					parent = rotate(gparent, key);
> 				t = rotate(ggparent, key);
> 				t->red = 0;
> 			}
> 			base->left->red = 0;
> 			
> 
> 			treesize++;
> 			return t;
> 		}
> 
> 
> 		//삭제 노드와 가장 가까운 빨강 씨앗을 찾아서 빨강 씨앗의 부모의 포인터 리턴
> 		//이 빨강 씨앗을 아래로 보내면서 삭제한다
> 		Node* find_seed(int key)
> 		{
> 			Node* del, *seed_parent, *parent;
> 			seed_parent = NULL;
> 			parent = base;
> 			del = base->left;
> 
> 			while(del != NULL) {
> 				if (key < del->key) {
> 					//빨강노드나 오른쪽 자식이 빨간 노드 찾기
> 					if (del->red || (del->right && del->right->red)) seed_parent = parent;
> 					parent = del;
> 					del = del->left;
> 				}
> 				else {
> 					//빨강노드나 왼쪽 자식이 빨간 노드 찾기
> 					if (del->red || (del->left && del->left->red)) seed_parent = parent;
> 					parent = del;
> 					del = del->right;
> 				}
> 			}
> 			return seed_parent;
> 		}
> 
> 
> 		//원하는 key값의 노드를 red 노드로 만든다.
> 		//red노드의 leaf노드만 삭제 가능 : 3노드나 4노드이기 때문
> 		void make_leaf_red(int key)
> 		{
> 			Node* seed_parent, *seed, *seed_child;
> 			seed_parent = find_seed(key);
> 
> 			if (seed_parent == NULL) {	//빨강 씨앗이 없으면
> 				seed_parent = base;
> 				seed = seed_parent->left;
> 				seed->red = 1;	//루트를 빨강으로 잠시 칠한다
> 			}
> 			else {
> 				//시드 설정
> 				if (key < seed_parent->key || seed_parent == base) seed = seed_parent->left;
> 				else seed = seed_parent->right;
> 			}
> 
> 			//씨앗이 빨강이 아니면 그 자식을 끌어 올린다.
> 			if (!seed->red) {
> 				if (key < seed->key) seed_child = seed->right;
> 				else seed_child = seed->left;
> 				seed->red = 1;
> 				seed_child->red = 0;
> 				seed_parent = rotate(seed_parent, seed_child->key);
> 			}
> 
> 			//외부노드가 아닐 동안
> 			while(seed->left && seed->right) {
> 				/*
> 				   printf("now seed's key value is [%c]\n", seed->key);
> 				   printf("now seed's left child's key value is [%c]\n", seed->left->key);
> 				   printf("now seed's right child's key value is [%c]\n", seed->right->key);
> 				   print(base, 0);
> 				   */
> 				seed->red = 0;
> 				seed->right->red = seed->left->red = 1;
> 
> 				if (key < seed->key) {
> 					//if ((seed->right->left || seed->right->right) && 
> 					//		(seed->right->left->red || seed->right->right->red)) {
> 					if ((seed->right->left && seed->right->left->red) ||
> 							(seed->right->right && seed->right->right->red)) {
> 						if (seed->right->left && seed->right->left->red) {	//RL회전
> 							seed->right->red = 0;
> 							rotate(seed, seed->right->left->key);
> 						}
> 						else {												//RR회전
> 							seed->right->right->red = 0;
> 						}
> 						rotate(seed_parent, seed->right->key);
> 					}
> 					seed_parent = seed;
> 					seed = seed->left;
> 				}
> 				else {
> 					//if ((seed->left->left || seed->left->right) &&
> 					//		(seed->left->left->red || seed->left->right->red)) {
> 					if ((seed->left->left && seed->left->left->red) ||
> 							(seed->left->right && seed->left->right->red)) {
> 						if (seed->left->right && seed->left->right->red) {	//LR회전
> 							seed->left->red = 0;
> 							rotate(seed, seed->left->right->key);
> 						}
> 						else {
> 							seed->left->left->red = 0;						//LL회전
> 						}
> 						rotate(seed_parent, seed->left->key);
> 					}
> 					seed_parent = seed;
> 					seed = seed->right;
> 				}
> 			}
> 		}
> 
> 
> 		//이 함수를 사용할 떄 반드시 원소가 레드블랙 트리 안에 있는지 체크해 보고 사용할 것!
> 		//없으면 서브트리의 크기가 뻑남
> 		//검색하고 시작하도록 해도 되지만 그냥 안했음
> 		//삭제가 실패하면 NULL 리턴
> 		Node* erase(int key)
> 		{
> 			Node* parent, *del, *center, *pcenter, *son;
> 			parent = base;
> 			del = base->left;
> 			//원소 찾기 : parent를 알아야 하기 때문에 search함수 안씀
> 			while(del != NULL && key != del->key) {
> 				del->treesize --;
> 				parent = del;
> 				if (key < del->key) del = del->left;
> 				else del = del->right;
> 			}
> 			if (del == NULL) return NULL;
> 			del->treesize --;
> 
> 			if (del->right && del->left) {	//내부 노드이면
> 				pcenter = del;	//삭제할 노드를 대체할 노드를 찾음
> 				center = del->right;
> 				while(center->left != NULL) {
> 					center->treesize--;
> 					pcenter = center;
> 					center = center->left; //center는 대체할 키임
> 				}
> 				del->key = center->key;	//삭제할 키를 대체할 키로 바꿈
> 				del = center;			//이제 center를 삭제하도록 조정
> 				parent = pcenter;
> 				key = del->key;
> 			}
> 
> 			if (del->left || del->right) {	//자식이 하나면 반드시 빨강
> 				if (del->left) son = del->left;
> 				else son = del->right;
> 				son->red = 0;
> 			}
> 			else if (del->left == NULL && del->right == NULL) {
> 				//자식이 없으면 빨강이면 삭제 검정이면 변환 후 삭제
> 				if (!del->red) make_leaf_red(del->key);
> 				son = NULL;
> 			}
> 			base->left->red = 0;
> 			if (key < parent->key || parent == base) parent->left = son;
> 			else parent->right = son;
> 			delete del;
> 
> 			treesize--;
> 			
> 			return parent;
> 		}
> 
> 		void printrecur(Node* node, int depth)
> 		{
> 			if (node == NULL) return;
> 			//for (int i = 0; i < depth; i++) printf("\t");
> 
> 			printf("%d ", node->key);
> 			/*
> 			if (node->red) printf("%c[R](size = %d)\n", (char)(node->key), node->treesize);
> 			else printf("%c[B](size = %d)\n", (char)(node->key), node->treesize);
> 			*/
> 
> 			printrecur(node->left, depth + 1);
> 			printrecur(node->right, depth + 1);
> 		}
> 
> 		void print()
> 		{
> 			printf("[");
> 			printrecur(base->left, 0);
> 			printf("]\n");
> 		}
> };
> 
> int n, m;
> int a[100000];
> struct query {
> 	int num;
> 	int l, r, rank;
> };
> bool operator < (const query& a, const query& b)
> {
> 	if (a.l == b.l) {
> 		return (a.r < b.r);
> 	}
> 	return (a.l < b.l);
> }
> query q[50000];
> int answer[50000];
> 
> int main()
> {
> 	scanf("%d%d", &n, &m);
> 	for (int i = 0; i < n; i++) {
> 		scanf("%d", &a[i]);
> 	}
> 
> 	for (int i = 0; i < m; i++) {
> 		scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].rank);
> 		if (q[i].l > q[i].r) {
> 			int temp = q[i].l; q[i].l = q[i].r; q[i].r = temp;
> 		}
> 		q[i].l--, q[i].r--;
> 		q[i].num = i;
> 		//printf("%d %d %d\n", q[i].l, q[i].r, q[i].rank);
> 	}
> 	sort(q, q + m);
> 
> 	RedBlack rb;
> 
> 	for (int i = q[0].l; i <= q[0].r; i++) {
> 		rb.insert(a[i]);
> 	}
> 	answer[q[0].num] = rb.rank(q[0].rank);
> 
> 	for (int i = 1; i < m; i++) {
> 		if (q[i - 1].r >= q[i].r) {
> 			(* (int *)0) = 0;
> 		}
> 		if (q[i - 1].r < q[i].l) {
> 			for (int j = q[i - 1].l; j <= q[i - 1].r; j++) rb.erase(a[j]);
> 			for (int j = q[i].l; j <= q[i].r; j++) rb.insert(a[j]);
> 		}
> 		else {
> 			for (int j = q[i - 1].l; j < q[i].l; j++) rb.erase(a[j]);
> 			for (int j = q[i - 1].r + 1; j <= q[i].r; j++) rb.insert(a[j]);
> 		}
> 		answer[q[i].num] = rb.rank(q[i].rank);
> 	}
> 
> 	for (int i = 0; i < m; i++) {
> 		printf("%d\n", answer[i]);
> 	}
> 
> 	return 0;
> }

• Re:~~-_-|', Long... 13K.(Inside) (442) insany 2006-03-15 16:55:46
• Re:~~-_-|', Long... 13K.(Inside) (442) insany 2006-03-15 17:32:27
• Finally, I got accepted (537) insany 2006-03-15 17:33:49