Problem Link: LightOJ :: 1339 — Strongest Community.

I am getting Wrong Answer but i can't find any bug in my logic. Can someone help me with my idea or provide me some test case please? It will be very helpful for me....

Problem Description, My Idea & My Code has been given below.

Thanks.

Problem Description: In a strange city, houses are built in a straight line one after another. There are several communities in the city. Each community consists of some consecutive houses such that every house belongs to exactly one community. The houses are numbered from 1 to n, and the communities are numbered from 1 to c.

Now some inspectors want to find the strongest community considering all houses from i to j. A community is strongest if maximum houses in the range belong to this community. So, there can be more than one strongest community in the range. So, they want to know the number of houses that belong to the strongest community. That's why they are seeking your help.

Input: Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case starts with a line containing three integers n (1 ≤ n ≤ 105), c (1 ≤ c ≤ n) and q (1 ≤ q ≤ 50000). The next line contains n space separated integers (each between 1 and c) denoting the communities the houses belong to. You can assume that the input follows the restrictions given above, and there are exactly c communities.

Each of the next q lines contains two integers i and j (1 ≤ i ≤ j ≤ n) denoting that the inspectors are asking for the result considering houses from i to j (inclusive).

Output: For each case, print the case number in a single line. Each of the next q lines should contain the number of houses that belong to the strongest community considering houses from i to j. The result should be listed in the same order as they are given in input.

Sample Input:

2

10 3 4
1 1 1 3 3 3 3 2 2 2
1 5
1 6
1 7
7 9

3 3 1
3 2 1
1 1

Output for Sample Input:

Case 1:
3
3
4
2
Case 2:
1

My Idea: I have implemented segment tree on community id.

I took all the query in a array named 'input' and sorted according the 'second' value. [ if, there are more points where second value is same, then point with lower value of 'first', will go before of other points (u can see in bool comp() function). ]

then I started the solution part: 'j' denotes the current position of input array, 'k' denotes last eliminated house no.
Starting from the house[0], I have increased the value of each house's community by +1. if any input[j].second is equal to 'i'th house then, I increased 'k' so that the value of 'k' is equal to input[j].first. While increasing 'k', I have added -1 to the community of 'k'th point, i.e. i have eliminated that house from consideration.

for each input[j] i took the result from tree[1] and stored it in 'ans' vector.

Then I sorted the answer according to query input id, and printed the answer. The logic should do the job, but yet it is giving me WA.

Can anyone help me finding where am i doing wrong?

My Code:

/**
 *    @author     : Maruf Tuhin
 *    @College    : CUET CSE 11
 *    @Topcoder   : the_redback
 *    @CodeForces : the_redback
 *    @UVA        : the_redback
 *    @link       : http://www.fb.com/maruf.2hin
 */

#include <bits/stdc++.h>

using namespace std;

typedef long long          ll;
typedef unsigned long long llu;

#define xx        first
#define yy        second
#define mp        make_pair
#define pb(x)     push_back(x)
#define all(x)    x.begin(),x.end()
#define allr(x)   x.rbegin(),x.rend()
#define mem(a,b)  memset(a,b,sizeof(a))
#define inf       1e9
#define eps       1e-9
#define mod       1000000007
#define NN        100002

#define read(a)   scanf("%lld",&a)

/**

*/
struct D
{
    ll x,y,in;
    D(ll X,ll Y,ll I) {
        x=X;
        y=Y;
        in=I;
    }
    D(){
    }
}input[NN];

ll tree[4*NN];
ll house[NN];
vector<pair<ll,ll> >ans;


void update(ll node, ll low, ll high, ll in , ll value)
{
    if(low==high && low==in )
    {
        tree[node] =tree[node]+value;
        return;
    }
    ll left = node<<1;
    ll right = left + 1;
    ll mid = (low + high)>>1;

    if(in <= mid)
        update(left, low, mid,in, value);
    else
        update(right, mid+1, high, in, value);

    tree[node]  = max(tree[left] , tree[right]);
}


bool comp(D a, D b)
{
    if(a.y==b.y)
        return a.x<b.x;
    return a.y<b.y;
}

int main()
{
    //ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef redback
        freopen("C:\\Users\\Maruf\\Desktop\\in.txt","r",stdin);
    #endif

    ll t=1,tc;
    read(tc);       ///Test case
    ll i,c,j,k,l,m,n;
    while(tc--)
    {
        read(n);
        read(c);
        read(m);

        mem(tree,0);

        for(i=1;i<=n;i++)
        {
            read(house[i]);
        }
        for(i=1;i<=m;i++)
        {
            read(k);
            read(l);
            input[i]=D(k,l,i);
        }

        sort(input+1,input+m+1,comp);
        ans.clear();

        j=1;
        k=1;
        for(i=1;i<=n;i++)
        {
            update(1,1,c,house[i],1);
            while(j<=m && input[j].y==i)
            {
                while(k<input[j].x)
                {
                    update(1,1,c,house[k],-1);
                    k++;
                }
                ll res=tree[1];
                ans.pb(mp(input[j].in,res));
                j++;
            }
        }
        sort(all(ans));
        printf("Case %lld:\n",t++);

        for(i=0;i<ans.size();i++)
        {
            printf("%lld\n",ans[i].yy);
        }
    }
    return 0;
}