Header Ad

HackerEarth Suarez problem solution

In this HackerEarth Suarez! problem solution You are given N segments [L, R], where L <= R . Now, you need to answer some queries based on these segments.

Overall, you need to answer Q queries. In each query you shall be given 2 integers K and X. You need to find the size of the Kth smallest segment that contains point X.

If no K segments contain point X, print 1 instead as the answer to that query.

A segment [L, R] is said to contain a point X if L <= X <= R. When we speak about the Kth smallest segment, we refer to the one having the Kth smallest size. We define the size of a segment to be the number of integral points it contains, i.e. R + 1 - L


HackerEarth Suarez ! problem solution


HackerEarth Suarez! problem solution.

import java.io.*;
import java.util.*;
import java.math.*;

public final class solution
{
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static FastScanner sc=new FastScanner(br);
static PrintWriter out=new PrintWriter(System.out);
static Random rnd=new Random();
static Pair[] a,b;
static Pair[][] al,qr;
static int[] size,c1,c2;
static int[] bit,cnt,res;
static int maxn=(int)(1e6+6);

static void update(int idx,int val)
{
while(idx<maxn)
{
bit[idx]+=val;idx+=idx&-idx;
}
}

static int query(int idx)
{
int ret=0;

while(idx>0)
{
ret=ret+bit[idx];idx-=idx&-idx;
}

return ret;
}

static void shuffle(int[] a)
{
for(int i=0;i<a.length;i++)
{
int next=rnd.nextInt(a.length);

int temp=a[i];a[i]=a[next];a[next]=temp;
}
}

public static void main(String args[]) throws Exception
{
int n=sc.nextInt();a=new Pair[n];size=new int[n];c2=new int[n];

if(n<1 || n>200000) throw new Exception("Wrong!");

for(int i=0;i<n;i++)
{
a[i]=new Pair(sc.nextInt(),sc.nextInt());

size[i]=a[i].r-a[i].l+1;c2[i]=size[i];

if(a[i].l<1 || a[i].r>(int)1e9 || a[i].l>a[i].r) throw new Exception("Wrong!");
}

int q=sc.nextInt();b=new Pair[q];c1=new int[n+n+q];int j=0;

if(q<1 || q>200000) throw new Exception("Wrong!");

for(int i=0;i<q;i++)
{
b[i]=new Pair(sc.nextInt(),sc.nextInt());

c1[j++]=b[i].r;

if(b[i].l<1 || b[i].l>n || b[i].r<1 || b[i].r>(int)(1e9)) throw new Exception("Wrong!");
}

for(int i=0;i<n;i++)
{
c1[j++]=a[i].l;c1[j++]=a[i].r;
}

shuffle(c1);shuffle(c2);Arrays.sort(c1);Arrays.sort(c2);cnt=new int[maxn];

for(int i=0;i<n;i++)
{
a[i].l=Arrays.binarySearch(c1,a[i].l);

a[i].r=Arrays.binarySearch(c1,a[i].r);

size[i]=Arrays.binarySearch(c2,size[i])+1;

cnt[a[i].l]++;cnt[a[i].r+1]++;
}

al=new Pair[maxn][];

for(int i=0;i<maxn;i++)
{
al[i]=new Pair[cnt[i]];cnt[i]=0;
}

for(int i=0;i<n;i++)
{
int curr1=a[i].l,curr2=a[i].r+1;

al[curr1][cnt[curr1]++]=new Pair(size[i],1);

al[curr2][cnt[curr2]++]=new Pair(size[i],-1);
}

qr=new Pair[maxn][];Arrays.fill(cnt,0);

for(int i=0;i<q;i++)
{
b[i].r=Arrays.binarySearch(c1,b[i].r);

cnt[b[i].r]++;
}

for(int i=0;i<maxn;i++)
{
qr[i]=new Pair[cnt[i]];cnt[i]=0;
}

for(int i=0;i<q;i++)
{
int curr=b[i].r;

qr[curr][cnt[curr]++]=new Pair(i,b[i].l);
}

bit=new int[maxn];res=new int[q];

for(int i=0;i<maxn;i++)
{
for(Pair x:al[i])
{
update(x.l,x.r);
}

for(Pair x:qr[i])
{
int k=x.r,low=1,high=maxn-1;

while(low<high)
{
int mid=(low+high)>>1;

if(query(mid)>=k)
{
high=mid;
}
else
{
low=mid+1;
}
}

res[x.l]=query(low)>=k?low:-1;
}
}

for(int i=0;i<q;i++)
{
int ans=res[i];

ans=ans==-1?ans:c2[ans-1];

out.println(ans);

if(ans==0 || ans<-1 || ans>(int)(1e9)) throw new Exception("Wrong!");
}

out.close();
}
}

class Pair implements Comparable<Pair>
{
int l,r;

public Pair(int l,int r)
{
this.l=l;this.r=r;
}

public int compareTo(Pair x)
{
return Integer.compare(this.r-this.l+1,x.r-x.l+1);
}
}

class FastScanner
{
BufferedReader in;
StringTokenizer st;

public FastScanner(BufferedReader in) {
this.in = in;
}

public String nextToken() throws Exception {
while (st == null || !st.hasMoreTokens()) {
st = new StringTokenizer(in.readLine());
}
return st.nextToken();
}

public String next() throws Exception {
return nextToken().toString();
}

public int nextInt() throws Exception {
return Integer.parseInt(nextToken());
}

public long nextLong() throws Exception {
return Long.parseLong(nextToken());
}

public double nextDouble() throws Exception {
return Double.parseDouble(nextToken());
}
}

Second solution

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <cstring>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> pip;
const int MAXN = 200005;
unordered_map <int,int> M;
vector <int> que[MAXN];
vector <pip> intervals;
int l[MAXN], r[MAXN], k[MAXN], x[MAXN], lo[MAXN], hi[MAXN], mid[MAXN], BIT[3*MAXN];
void BIT_upd(int pos, int val)
{
while(pos < 3*MAXN)
{
BIT[pos]+=val;
pos+=(pos & (-pos));
}
}
int BIT_get(int pos)
{
int ret = 0;
while(pos > 0)
{
ret+=BIT[pos];
pos-=(pos & (-pos));
}
return ret;
}
int main()
{
int n;
scanf("%d", &n);
vector <int> nums;
for (int i = 0; i < n; ++i)
{
scanf("%d %d", &l[i], &r[i]);
nums.push_back(l[i]);
nums.push_back(r[i]);
}
int q;
scanf("%d", &q);
for (int i = 0; i < q; ++i)
{
scanf("%d %d", &k[i], &x[i]);
nums.push_back(x[i]);
}
sort(nums.begin(), nums.end());
nums.resize(unique(nums.begin(), nums.end()) - nums.begin());
for (int i = 0; i < nums.size(); ++i)
{
M[nums[i]] = i + 1;
}
for (int i = 0; i < n; ++i)
{
intervals.push_back(pip(r[i] + 1 - l[i], pii(M[l[i]],M[r[i]])));
}
sort(intervals.begin(), intervals.end());
for (int i = 0; i < q; ++i)
{
lo[i] = 0;
hi[i] = n;
mid[i] = (lo[i] + hi[i])/2;
que[mid[i]].push_back(i);
}
bool changed = true;
while(changed)
{
changed = false;
memset(BIT, 0, sizeof BIT);
for (int i = 0; i < n; ++i)
{
int l = intervals[i].second.first, r = intervals[i].second.second;
BIT_upd(l,1);
BIT_upd(r+1,-1);
while(!que[i].empty())
{
int qnum = que[i].back();
que[i].pop_back();
int pos = M[x[qnum]];
if(BIT_get(pos) >= k[qnum])
hi[qnum] = mid[qnum];
else
lo[qnum] = mid[qnum] + 1;
if(lo[qnum] < hi[qnum])
{
changed = true;
mid[qnum] = (lo[qnum] + hi[qnum])/2;
que[mid[qnum]].push_back(qnum);
}
}
}
}
for (int i = 0; i < q; ++i)
{
if(lo[i] >= n)
printf("-1\n");
else
printf("%d\n", intervals[lo[i]].first);
}
return 0;
}

Post a Comment

0 Comments