Header Ad

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


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';
}
}


Post a Comment

0 Comments