Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #define MAX 1000000005
- int size, queries, temp, count, idx, weight;
- struct node{
- int key;
- int count;
- int smaller;
- struct node *left, *right;
- };
- void inorder(struct node *root){
- if(root!=NULL){
- inorder(root->left);
- printf("%d(%d) --> %d\n", root->key, root->count, root->smaller);
- inorder(root->right);
- }
- }
- void modifyWeight(struct node *root){
- if(root!=NULL){
- modifyWeight(root->right);
- root->smaller = size-(weight++);
- modifyWeight(root->left);
- }
- }
- struct node *newNode(int item){
- struct node *temp = (struct node*)malloc(sizeof(struct node));
- temp->key = item;
- temp->left = temp->right = NULL;
- temp->count = 1;
- return temp;
- }
- struct node* insert(struct node* node, int key){
- if(node==NULL){
- return newNode(key);
- }
- if(key < node->key){
- node->left = insert(node->left, key);
- }else if(key > node->key){
- node->right = insert(node->right, key);
- }else if(key == node->key){
- (node->count)++;
- }
- return node;
- }
- int findWeight(struct node *root, int key){
- //printf("Node now %d\n", root->key);
- if(root==NULL){
- return -1;
- }
- if(root->key<=key){
- return root->smaller;
- }
- if(root->key>key){
- return findWeight(root->left, key);
- }
- }
- int main(){
- scanf("%d %d",&size ,&queries);
- struct node *root = NULL;
- root = insert(root, MAX);
- for(int i=0;i<size;i++){
- scanf("%d", &temp);
- insert(root, temp);
- }
- modifyWeight(root);
- inorder(root);
- for(int i=0;i<queries;i++){
- count = 0;
- scanf("%d", &temp);
- findWeight(root, temp);
- printf("Out : %d\n", findWeight(root, temp));
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement