Here you will find solutions of many problems on spoj. If you want solution of some problem which is not listed in blog or have doubt regarding any spoj problem (which i have solved) or any programming concept (data structure) you can mail me @ raj.nishant360@gmail.com
And my humble request to you all that don't copy the code only try to understand the logic and algorithm behind the code. I have started this because if you tried as hard as you can and still can't find any solution to the problem then you can refer to this.
You can read my answer how to start competitive programming CLICK HERE

Saturday, February 28, 2015

ORDERSET-Order statistic set

Order statistic set

Given below code is for ORDERSET spoj or Order statistics set spoj.

Explanation :- Here I have used Policy Based Data Structure of C++ ,  You can read about this Design , Using & Testing. And it support all basic STL functions and some extra of it owns.
Time :- 0.65 sec



#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<
int ,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>pbd_set;
int main(){
    pbd_set s;
    int t;
    scanf("%d ",&t);
    while(t--){
        char typ;
        int n;
        scanf(" %c%d",&typ , &n);
        if(typ == 'I')
            s.insert(n);
        else if (typ == 'D')
            s.erase(n);
        else if (typ == 'K'){
            int ans;
            n--;
            if(s.find_by_order(n) != s.end()){
                ans = *s.find_by_order(n);
                printf("%d\n",ans);
            }
            else 
                printf("invalid\n");
        }
        else{
            int ans = s.order_of_key(n);
            printf("%d\n",ans);
        }
    }
    return 0;
}



My solution for ORDERSET spoj or Order statistic set spoj problem using BIT(Binary Index Tree)
Time:- 0.46 sec


#include <bits/stdc++.h>
using namespace std;
#define MAX 200005
#define pb push_back
int tree[200009], hash[200009], save[200009];
void update(int pos , int data){
    while(pos <= MAX){
        tree[pos]+= data;
        pos += (pos & (-pos));
    }
}
int read(int pos){
    int ans = 0;
    while(pos){
        ans += tree[pos];
        pos -= (pos & -pos);
    }
    return ans;
}
struct data{
    int pos , data , hash;
    char type;
};
data d[200009], query[200009];
bool cmp(const data &a , const data &b){
    return a.data == b.data ? a.pos < b.pos : a.data < b.data;
}
int b_search(int k){

    int low = 0 , high = 200000 , mid;
    while(low < high){
        mid = (low + high)>>1;
        if(read(mid) >= k)
            high = mid;
        else
            low = mid+1;
    }
    return low;
}
int main(){
    int q ;
    scanf("%d",&q);
    for(int i = 0 ; i < q ; i++){
        scanf(" %c%d",&d[i].type , &d[i].data);
        d[i].pos = i+1;
    }

    sort(d , d + q , cmp);
    
    int cnt = 1 , prev = d[0].data;
    d[0].hash = cnt;
    save[cnt]= d[0].data;
    for(int i = 1 ; i < q ; i++)
    {
        if(prev != d[i].data){
            prev = d[i].data;
            cnt++;
            d[i].hash = cnt;
            save[cnt] = d[i].data;
        }
        else
            d[i].hash = cnt;
    }

    
    for(int i = 0 ; i < q ; i++){
        query[d[i].pos] = d[i];
    }

    cnt = 0;
    for(int i = 1 ; i <= q ; i++){
        if(query[i].type == 'I'){
            if(!hash[query[i].hash]){
                cnt++;
                hash[query[i].hash] = 1;
                update(query[i].hash , 1);
            }
        }
        else if(query[i].type == 'D'){

            if(hash[query[i].hash]){
                cnt--;
                hash[query[i].hash] = 0;
                update(query[i].hash , -1);
            }
        }

        else if(query[i].type == 'K'){
            if(query[i].data > cnt)
                printf("invalid\n");
            else
                printf("%d\n",save[b_search(query[i].data)]);
        }
        else
            printf("%d\n",read(query[i].hash - 1));
    }
    return 0;
}



My solution for ORDERSET spoj or Order statistic set spoj using Height Balanced Tree(AVL Tree ) I copied AVL tree code from geeks for geeks . For learning AVL tree you can refer to geeks for geeks :- http://www.geeksforgeeks.org/avl-tree-set-2-deletion/
Time :- 0.67 sec


#include <bits/stdc++.h>
using namespace std;
class node{
public:
 int val , height , sum ;
 node * left , *right;
    node(){
        val = height = sum = 0;
        left = right = NULL;    
    }
};
int get_sum(node *x){
    
    if(x == NULL)
        return 0;
    return x->sum;
}
node *get_new_node(int key){

    node *temp = new node();
    temp->val =  key;
 temp->left = NULL;
 temp->right = NULL;
 temp->height = 1;
 temp->sum = 1;
    return temp;
}

bool find(int key , node *root){
 
 if(root == NULL)
  return false;
 if(key < root->val)
  return find(key , root->left);
 else if(key > root->val)
  return find(key , root->right);
 else
  return true;
}

int get_height(node *x){
 
 if(x==NULL)
  return 0;
 return x->height;
}

int get_diff(node *x){

    if(x == NULL)
        return 0;
    return get_height(x->left) - get_height(x->right);
}
node *left_rotate(node *x){
 
 node *y  = x->right;
 node *y_left = y->left;

 y->left = x;
 x->right = y_left;

 x->height = max(get_height(x->left) , get_height(x->right)) + 1;
    x->sum = get_sum(x->left) + get_sum(x->right) + 1;
    y->height = max(get_height(y->left) , get_height(y->right)) + 1;
    y->sum = get_sum(y->left) + get_sum(y->right) + 1;
    return y;
}

node *right_rotate(node *x){

    node *y = x->left;
    node *y_right = y->right;

    y->right = x;
    x->left = y_right;
    
    x->height = max(get_height(x->left) , get_height(x->right)) + 1;
    x->sum = get_sum(x->left) + get_sum(x->right) + 1;
    y->height = max(get_height(y->left) , get_height(y->right)) + 1;
    y->sum = get_sum(y->left) + get_sum(y->right) + 1;
    return y;
}
node *insert(node *root , int key){

    if(root == NULL)
        return get_new_node(key);

    if(key < root->val)
        root->left = insert(root->left , key);

    else
        root->right = insert(root->right , key);

    root->height = max(get_height(root->left) , get_height(root->right)) + 1;
    root->sum = get_sum(root->left) + get_sum(root->right) + 1;
    int diff ;
    if(root == NULL)
        diff = 0;
    else
        diff = get_height(root->left) - get_height(root->right);

    if(diff > 1 && key < root->left->val)
        return right_rotate(root);
    if(diff < -1 && key > root->right->val)
        return left_rotate(root);
    if(diff > 1 && key > root->left->val){
        root->left = left_rotate(root->left);
        return right_rotate(root);
    }
    if(diff < -1 && key < root->right->val){
        root->right = right_rotate(root->right);
        return left_rotate(root);    
    }
    
    return root;
}
node *del(node * root , int key){

    if(root == NULL)
        return root;
    
    if(key < root->val)
        root->left = del(root->left , key);
    else if(key > root->val)
        root->right = del(root->right , key);

    else{
        
        if(root->left == NULL || root->right == NULL){
            
            node *temp = root->left ? root->left : root->right;
            if(temp == NULL){
                
                temp = root;
                root = NULL;
            }
            else
                *root = *temp;        
        }
        else{
            
            node *temp = root->right;
            while(temp->left != NULL)
                temp = temp->left;
            
            root->val = temp->val;

            root->right = del(root->right , temp->val);        
        }
    }
    
    if(root == NULL)
        return root;
    root->height = max(get_height(root->left) , get_height(root->right)) + 1;
    root->sum = get_sum(root->left) + get_sum(root->right) + 1;
    int diff = get_height(root->left) - get_height(root->right);
    
    if (diff > 1 && get_diff(root->left) >= 0)
        return right_rotate(root);
 
    if (diff > 1 && get_diff(root->left) < 0)
    {
        root->left =  left_rotate(root->left);
        return right_rotate(root);
    }
 
    if (diff < -1 && get_diff(root->right) <= 0)
        return left_rotate(root);
 
    if (diff < -1 && get_diff(root->right) > 0)
    {
        root->right = right_rotate(root->right);
        return left_rotate(root);
    }
    return root;
}
int get_by_order(node *root , int key){

    if(root == NULL)
        return 0;
    int left_size = get_sum(root->left);
    if(left_size == key)
        return root->val;
    if(key < left_size)
        return get_by_order(root->left , key);
    else
        return get_by_order(root->right , key - left_size - 1);
}
int order_of_key(node *root , int key){

    if(root == NULL)
        return 0;

    if(key < root->val)
        return order_of_key(root->left , key);
    else if(key == root->val){
        if(root->left != NULL)
            return get_sum(root->left) + 1;
        else 
            return 1;
    }
    else
    {
        if(root->left != NULL )
            return get_sum(root->left) + 1 + order_of_key(root->right , key);
        else
            return 1 + order_of_key(root->right , key);
    }
}

int main(){
    
    int q;
    scanf("%d",&q);
    node *root = NULL;
    while(q--){

        char c ;
        int value;
        scanf(" %c%d",&c , &value);
        if(c=='I'){

            if(!find(value , root)){
                root = insert(root , value) ;
            }
        }
        else if(c == 'D'){
            root = del(root , value ) ;
        }
        else if(c == 'C'){
            int ans = order_of_key(root , value);
            if(find(value , root))
                printf("%d\n",ans - 1);
            else
                printf("%d\n",ans);
        }
        else
        {
            value--;
            if(root == NULL)
                printf("invalid\n");
            else if( root->sum <= value)
                printf("invalid\n");
            else
                printf("%d\n",get_by_order(root , value));
        }
    }
    return 0;
}