SPOJ Problem -Frequent . Receiving WA .

Revision en1, by watchdogs132, 2020-04-02 13:11:04

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;
} 
Tags #segment tree, #spoj, #wronganswer, #wrongverdict

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)