SPOJ Problem -Frequent . Receiving WA [Solved].
Difference between en2 and en3, changed 8 character(s)
Link to problem:  https://www.spoj.com/problems/FREQUENT/↵

I know this is quite a famous problem and I have searched extensively about it , but my attempts at debugging my code have failed. ↵

I use the approach of Segment Trees to solve this problem after having built a frequency array.↵
Run time : $O(n)$ pre-processing per test case and $O(log (n))$ to answer each query.↵

~~~~~↵
#include<iostream>↵
#include<algorithm>↵
#include<unordered_map>↵
 ↵
using namespace std;↵
 ↵
const int N=200000;↵
 ↵
int a[N],t[4*N],b[N]; //b is the frequency array↵
 ↵
void build(int v,int tl,int tr){↵
    if(tl==tr){↵
        t[v]=b[tl];↵
    }↵
    else{↵
    int tm=(tl+tr)/2;↵
    build(2*v,tl,tm);↵
    build(2*v+1,tm+1,tr);↵
    t[v]=max(t[2*v],t[2*v+1]);↵
    }↵
}↵
 ↵
int query(int v,int tl,int tr,int l,int r){↵
    if(l>r)↵
        return -1e9;↵
    if(l<=tl&&tr<=r)↵
        return t[v];↵
    int tm=(tl+tr)/2;↵
    return max(query(v*2, tl, tm, l, min(r, tm)),↵
               query(v*2+1, tm+1, tr, max(l, tm+1), r));↵
}↵
int main()↵
{↵
      int n,q; ↵
      while(true){↵
        scanf("%d", &n);↵
        if(!n)break;↵
        scanf("%d", &q);↵
        unordered_map<int,int>cnt;↵
        for(int i=0;i<n;i++){↵
            scanf("%d",&a[i]);↵
            ++cnt[a[i]];↵
        }↵
        for(int i=0;i<n;i++){↵
            b[i]=cnt[a[i]];↵
        }↵
        build(1,0,n-1);↵
         while(q--){↵
            int l,r;↵
            scanf("%d %d",&l,&r);↵
            --l,--r;↵
            if(a[r]==a[l]){  //This is when all numbers in the range are the same.↵
                printf("%d\n",r-l+1);↵
            }↵
            else{↵
                /*This is to handle the case as follows :111 22233 4444↵
                  idx1 and idx2-1 will cover the range 22233 and↵
                  then we do the max of all three blocks [111] [22233] [4444] which↵
                  in this case is basically max(3,3,4)=4 */↵
                int idx1=upper_bound(a+l,a+l+r,a[l])-a;↵
                int idx2=lower_bound(a+l,a+l+r,a[r])-a;↵
                int ans=max(max(idx1-l,r+1-idx2),query(1,0,n-1,idx1,idx2-1));↵
                printf("%d\n",ans);↵
            }↵
         }↵
    }↵
 return 0;↵
} ↵
~~~~~↵



History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English watchdogs132 2020-04-03 18:23:03 8 Solved
en2 English watchdogs132 2020-04-02 16:04:07 1 Tiny change: ' problem: https://w' -> ' problem: https://w'
en1 English watchdogs132 2020-04-02 13:11:04 2259 Initial revision (published)