HackerEarth Number of Balloons problem solution

In this HackerEarth Number of Balloons problem solution, You have arranged balloons in a linear order. Every balloon is colored and the ith balloon’s color is represented by Ci. Here, the color of balloons is depicted with numbers.

The number k is not a suitable number, therefore you decide to use it for the less number of times. You do not contain any range of ballons in which a color repeats exactly k times. If the displayed balloons are numbered from b0,b1,b2,…,bn-1, then the range of balloons from l to r is bl,b1+1,bl+2,…br.

You are provided with some specific ranges and your task is to determine the number of colors that get repeated for exactly k times in each range that is provided.

HackerEarth Number of Balloons problem solution.

#include<bits/stdc++.h>
#include<fstream>

using namespace std;
const int maxn=1e5+10;
int a[maxn],n,seg[3][20][maxn],mk[maxn],b[maxn];
map<int,vector<int> > mark;

void pre(){
  for(int i=1;i<=n;i++){
    mark[a[i]].push_back(i);
  }
}

struct segment{
  int ans=0,num=0;
  map<int,int> mk;
  segment(int x1,int x2){
    num=x2;
    for(int i=1;i<=n;i++)
      b[i]=0;
    for(int i=1;i<=n;i++)
      if(!mk[a[i]]){
    mk[a[i]]=1;
    for(int j=0;j<mark[a[i]].size();j++)
      if(j>=x1)
        b[mark[a[i]][j]]=mark[a[i]][j-x1];
      else
        b[mark[a[i]][j]]=-1;
      }
    make_seg(1,n,1);
  }
  
  void make_seg(int l,int r,int len)
  {
    if(l==r){
      seg[num][len][l]=b[l];
      return ;
    }
    int mid=(l+r)/2;
    make_seg(l,mid,len+1);
    make_seg(mid+1,r,len+1);
    merge(seg[num][len+1]+l,seg[num][len+1]+mid+1,seg[num][len+1]+mid+1,seg[num][len+1]+r+1,seg[num][len]+l);
  }

  int bs(int l,int r,int k,int len)
  {
    if(l==r){
      if(seg[num][len][l]>=k)
    return 0;
      return l;
    }
    int mid=(l+r+1)/2;
    if(seg[num][len][mid]<k)
      return bs(mid,r,k,len);
    else
      return bs(l,mid-1,k,len);
  }

  void ans_seg(int l,int r,int s,int f,int len)
  {
    if(f<l || r<s)
      return;
    if(s<=l && r<=f){
      int x=bs(l,r,s,len);
      if(x!=0)
    ans+=x-l+1;
      return;
    }
    int mid=(l+r)/2;
    ans_seg(l,mid,s,f,len+1);
    ans_seg(mid+1,r,s,f,len+1);
  }

};

int main()
{
  int k,q;
  cin>>n>>k>>q;
  for(int i=1;i<=n;i++)cin>>a[i];
  pre();
  segment a(k+1,0);
  segment b(k,1);
  segment c(k-1,2);
  int ans=0;
  while(q--){
    int l,r;
    cin>>l>>r;
    l=(l+ans)%n;
    r=(r+ans)%n;
    l++;
    r++;
    if(r<l)
      swap(l,r);
    a.ans_seg(1,n,l,r,1);
    b.ans_seg(1,n,l,r,1);
    c.ans_seg(1,n,l,r,1);
    ans=(b.ans-c.ans)-(a.ans-b.ans);
    cout<<ans<<endl;
    a.ans=0;b.ans=0;c.ans=0;
  }
}

Second solution

#include<bits/stdc++.h>
using namespace std;
int n;

namespace segment{
    const int maxn = 1e7; // TODO
    int eof = 1;
    int L[maxn], R[maxn], seg[maxn];
    
    int add(int v, int x, int root, int st = 0, int en = n){
    assert(eof<maxn);
    
    seg[eof] = seg[root] + x;
    L[eof] = L[root];
    R[eof] = R[root];
    root = eof++;
    
    if(en - st < 2)
        return root;
    int mid = (st + en) >> 1;
    if(v < mid)
        L[root] = add(v, x, L[root], st, mid);
    else
        R[root] = add(v, x, R[root], mid, en);
    return root;
    }

    int get(int l, int r, int root, int st = 0, int en = n){
    if(l <= st && en <= r)
        return seg[root];
    if(r <= st || en <= l)
        return 0;
    int mid = (st + en) >> 1;
    return get(l, r, L[root], st, mid) +
        get   (l, r, R[root], mid, en);
    }
}

const int maxn = 1e5 + 10;
int k, q, ar[maxn];
int l[maxn], r[maxn];

void init(){
    cin >> n >> k >> q;
    vector<int> vc;
    for(int i = 0; i < n; i++)
    cin >> ar[i], vc.push_back(ar[i]);
    sort(vc.begin(), vc.end());
    vc.resize(unique(vc.begin(), vc.end()) - vc.begin());
    for(int i = 0; i < n; i++)
    ar[i] = lower_bound(vc.begin(), vc.end(), ar[i]) - vc.begin();
    for(int i = 0; i < q; i++)
    cin >> l[i] >> r[i];
}

vector<int> vc[maxn];
int root[maxn];

inline void add(const int &v,const int &x,int &node){
    if(vc[v].size() >= k)
    node = segment::add(vc[v][vc[v].size() - k], x, node);
    if(vc[v].size() > k)
    node = segment::add(vc[v][vc[v].size() - k - 1], -x, node);
}

void build(){
    int node = 0;
    for(int i = 0; i < n; i++){
    add(ar[i], -1, node);
    vc[ar[i]].push_back(i);
    add(ar[i], +1, node);
    root[i] = node;
    }
}

int main(){
    init();
    build();
    int ans = 0;
    for(int i = 0; i < q; i++){
    l[i] = (l[i] + ans) % n;
    r[i] = (r[i] + ans) % n;
    if(l[i] > r[i])
        swap(l[i], r[i]);
    ans = segment::get(l[i], r[i] + 1, root[r[i]]);
    cout << ans << 'n';
    }
}

coding problems solutions