D-query :spoj (MO) (for only queries in range )

-
                                              http://www.spoj.com/problems/DQUERY/en/
                                         

DQUERY - D-query



In this question , the concept of rearranging queries is used , the method known as "MO". 
In the question, it is asked to find total different numbers present in the range [l,r] . "add" and "del" functions are written accordingly.





#include<bits/stdc++.h>

using namespace std;

int readInt () {
bool minus = false;
int result = 0;
char ch;
ch = getchar();
while (true) {
if (ch == '-') break;
if (ch >= '0' && ch <= '9') break;
ch = getchar();
}
if (ch == '-') minus = true; else result = ch-'0';
while (true) {
ch = getchar();
if (ch < '0' || ch > '9') break;
result = result*10 + (ch - '0');
}
if (minus)
return -result;
else
return result;
}


struct node
{
 int lf,rt,qno;
};

int bck_sz,ans=0;

bool cmp(struct node a,struct node b)
{
    int  i,j;
    i=a.rt/bck_sz;
    j=b.rt/bck_sz;
    if(i==j)
    {
        if(a.lf<b.lf)
            return 1;
        else
            return 0;
    }
    else{
        if(i<j)
            return 1;
        else
            return 0;
    }
}



int has[1000005];
 
void add(int num)
{
if(has[num]==0)
{
ans++;
has[num]=1;
}
else
 has[num]++;
}


void del(int num)
{
if(has[num]==1)
{
ans--;
has[num]=0;
}
else if(has[num]>1)
   has[num]--;
}



int main()
{
int n,i,j,k,l,r,q,x,y;
n=readInt();
int arr[n+1];
for(i=1;i<=n;i++)
arr[i]=readInt();
   
     bck_sz=sqrt(n);
 
q=readInt();
int result[q];
node a[q];
for(i=0;i<q;i++)
{
l=readInt();
r=readInt();
a[i].lf=l;
a[i].rt=r;
a[i].qno=i;
}

   sort(a,a+q,cmp);

  // for(i=0;i<q;i++)
    //cout<<a[i].lf<<" "<<a[i].rt<<endl;

l=1,r=0;
for(i=0;i<q;i++)
{
    x=a[i].lf;
    y=a[i].rt;
    while(r<y)
    {
 
        r++;
        add(arr[r]);
    }
    while(l>x)
    {
        l--;
        add(arr[l]);
    }
    while(l<x)
    {
        del(arr[l]);
        l++;
    }
    while(r>y)
    {
        del(arr[r]);
        r--;
    }
    result[a[i].qno]=ans; 
}


 for(i=0;i<q;i++)
  printf("%d\n",result[i]);

return 0;
}

Comments

Post a Comment

Popular posts from this blog

Getting Started With MEAN App Development with AngularJs , ExpressJs , NodeJs and MongoDB.

-
          Getting Started With MEAN App Development I Started Learning AngularJs one year Back. It is always a nice experience to start learning something new. I used Some of my AngularJs skills in my Programming Calculator App. ( https://nikhilnihal.github.io/programmingcalculator/index.html ) Few Days Back , I Started my hands on NodeJs and ExpressJs. I watched many Youtube Videos and Tutorials of  NodeJs and ExpreesJs. After that , I thought to do a Small Project Using all my skills of AngularJs , NodeJs ,ExpressJs.  I followed a Youtube Video ( https://www.youtube.com/watch?v=kHV7gOHvNdk ) and Made a Small Project Similiar to this one.After that I also Learnt that how to deploy my MEAN app on heroku website( heroku.com ). My app uses MongoDB for database. So , i also used mLab ( https://mlab.com /),which provided me MongoDB hosting service. There is a very useful blog which helped me to learn how to deploy my app on heroku. ( ht...
Read more

B. Dreamoon and WiFi :calculate no. of ways : recursive solution (branch and bound )

-
http://codeforces.com/contest/476/problem/B #include < bits / stdc ++. h > using namespace std ; string s1 , s2 ; int val = 0 , n ; int dp [ 15 ][ 15 ]; int solve ( int s , int l , int f ) { int & ret = dp [ s ][ l ]; if ( s == l ) { if ( f == val ) return 1 ; else return 0 ; } int ct = 0 ; ///number of ways in starting is 0 if ( s2 [ s ]== '+' ) ct += solve ( s + 1 , l , f + 1 ); if ( s2 [ s ]== '-' ) ct += solve ( s + 1 , l , f - 1 ); if ( s2 [ s ]== '?' ) ct += solve ( s + 1 , l , f + 1 )+ solve ( s + 1 , l , f - 1 ); return ret = ct ; /// In the last return this value } int main () { int i , j , k , l ; double ans ; cin >> s1 >> s2 ; n = s1 . size (); for ( i = 0 ; i < n ; i ++) { if ...
Read more

A. Dreamoon and Stairs : minimum steps to reach : recursion solution.

-
http://codeforces.com/contest/476/problem/A #include < bits / stdc ++. h > using namespace std ; int dp [ 10001 ][ 5055 ]; int fun ( int cu , int n , int m , int st ) { if ( st % m == 0 && cu == n ) { // cout<<st<<endl; return st ; } if ( cu > n || st > n || st > 5050 ) return 999999 ; int & ret = dp [ cu ][ st ]; if ( ret ) return ret ; int k1 = fun ( cu + 1 , n , m , st + 1 ); int k2 = fun ( cu + 2 , n , m , st + 1 ); return ret = min ( k1 , k2 ); } int main () { int n , m , i , j , k , l ; cin >> n >> m ; //if(n>m*2) // cout<<-1<<endl; k = fun ( 0 , n , m , 0 ); if ( k == 999999 ) cout <<- 1 << endl ; else cout << k << endl ; return 0 ; }
Read more