Almost Equal - Advanced
Problem Statement :
A Sumo wrestling championship is scheduled to be held this winter in the HackerCity where N wrestlers from different parts of the world are going to participate. The rules state that two wrestlers can fight against each other if and only if the difference in their height is less than or equal to K, (i.e) wrestler A and wrestler B can fight if and only if |height(A)-height(B)|<=K. Given an array H[], where H[i] represents the height of the ith fighter, for a given l, r where 0 <= l <= r < N, can you count the number of pairs of fighters between l and r (both inclusive) who qualify to play a game? Input Format The first line contains an integer N and K separated by a single space representing the number of Sumo wrestlers who are going to participate and the height difference K. The second line contains N integers separated by a single space, representing their heights H[0] H[1] ... H[N - 1]. The third line contains Q, the number of queries. This is followed by Q lines each having two integers l and r separated by a space. Output Format For each query Q, output the corresponding value of the number of pairs of fighters for whom the absolute difference of height is not greater that K. Constraints 1 <= N <= 100000 0 <= K <= 109 0 <= H[i] <= 109 1 <= Q <= 100000 0 <= l <= r < N
Solution :
Solution in C :
In C++ :
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <map>
#include <set>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,102400000")
int n, K;
struct element
{
int val;
int index;
bool operator <(element that) const
{
return val < that.val;
}
}E[100001];
int toLeft[100001], toRight[100001];
int indexToRank[100001];
int s[1000001];
int lowbit(int x){return x&(-x);}
inline void update(int pos, int v)
{
while(pos <= n)
{
s[pos] += v;
pos += lowbit(pos);
}
}
inline int query(int pos)
{
int ret = 0;
while(pos)
{
ret += s[pos];
pos -= lowbit(pos);
}
return ret;
}
int SQRTN = 330;
int nQuery;
long long ans[100001];
struct query
{
int L, R;
int index;
bool operator <(query that) const
{
if(L / SQRTN != that.L / SQRTN)
return L / SQRTN < that.L / SQRTN;
if((L / SQRTN) % 2 == 0)
return R / SQRTN < that.R/SQRTN;
return R / SQRTN > that.R/SQRTN;
}
}Q[100001];
int curL = 1, curR = 0;
long long curAns = 0;
inline long long evaluation()
{
long long ret = 0;
for(int i = 2; i <= nQuery; i++)
ret += abs(Q[i].L - Q[i-1].L) + abs(Q[i].R - Q[i-1].R);
return ret;
}
inline void addIt(int x)
{
x = indexToRank[x];
curAns += query(toRight[x]) - query(toLeft[x]-1);
update(x, 1);
}
inline void delIt(int x)
{
x = indexToRank[x];
update(x, -1);
curAns -= query(toRight[x]) - query(toLeft[x]-1);
}
int MAIN()
{
scanf("%d %d", &n, &K);
//cin >> n >> K;
for(int i = 1; i <= n; i++)
{
scanf("%d", &E[i].val);
//cin >> E[i].val;
E[i].index = i;
}
sort(E + 1, E + 1 + n);
for(int i = 1; i <= n; i++)
indexToRank[E[i].index] = i;
int p = 1;
for(int i = 1; i <= n; i++)
{
while(E[i].val - E[p].val > K) p ++;
toLeft[i] = p;
}
p = n;
for(int i = n; i >= 1; i--)
{
while(E[p].val - E[i].val > K) p --;
toRight[i] = p;
}
scanf("%d", &nQuery);
//cin >> nQuery;
for(int i = 1; i <= nQuery; i++)
scanf("%d %d", &Q[i].L, &Q[i].R), Q[i].index = i;
//cin >> Q[i].L >> Q[i].R, Q[i].index = i;
int old_sqrtN = SQRTN;
long long bestSqurn = 0, bestV = 1000000000000LL;
for(int i = old_sqrtN - 20; i <= old_sqrtN + 20; i += 10)
{
SQRTN = i;
sort(Q + 1, Q + 1 + nQuery);
long long v = evaluation();
if(v < bestV)
{
bestV = v;
bestSqurn = i;
}
}
SQRTN = bestSqurn;
sort(Q + 1, Q + 1 + nQuery);
memset(s, 0, sizeof(s));
for(int i = 1; i <= nQuery; i++)
{
//cout << Q[i].index << endl;
int L = Q[i].L + 1, R = Q[i].R + 1;
if(curL > R || curR < L)
{
while(curL <= curR)
{
delIt(curL);
curL ++;
}
curL = L;
curR = L-1;
}
while(curR < R)
{
addIt(curR + 1);
curR += 1;
}
while(curL > L)
{
addIt(curL - 1);
curL --;
}
while(curR > R)
{
delIt(curR);
curR --;
}
while(curL < L)
{
delIt(curL);
curL ++;
}
ans[Q[i].index] = curAns;
//cout << curAns << endl;
}
for(int i = 1; i <= nQuery; i++)
printf("%lld\n", ans[i]);
//cout << ans[i] << endl;
return 0;
}
int main()
{
#ifdef LOCAL_TEST
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
//ios :: sync_with_stdio(false);
//cout << fixed << setprecision(16);
return MAIN();
}
In Java :
import java.io.*;
import java.util.*;
public class Solution {
static int nn;
static int block;
static int[] fenwick;
static long cnt = 0;
static class B implements Comparable<B> {
int l;
int r;
int id;
@Override
public int compareTo(B o) {
int i = l/block;
int j = o.l/block;
if (i != j) {
return i - j;
}
if (r != o.r) {
return r - o.r;
}
return l - o.l;
}
}
static int getSum(int x) {
int s = 0;
for (; x != 0; x &= x-1)
s += fenwick[x-1];
return s;
}
static class Node {
int l;
int r;
int h;
public Node(int l, int r, int h) {
this.l = l;
this.r = r;
this.h = h;
}
void remove() {
add(h, -1);
cnt -= getSum(r) - getSum(l);
}
void add() {
cnt += getSum(r) - getSum(l);
add(h, 1);
}
void add(int x, int v) {
for (; x < nn; x |= x+1)
fenwick[x] += v;
}
}
static public int lowerBound(int[] arr, int len, int key) {
if (key <= arr[0]) {
return 0;
}
if (key > arr[len - 1]) {
return 0;
}
int index = Arrays.binarySearch(arr, 0, len, key);
if (index < 0) {
index = - index - 1;
if (index < 0) {
return 0;
}
}
return index;
}
static public int upperBound(int[] arr, int len, int key) {
int index = Arrays.binarySearch(arr, 0, len, key+1);
if (index < 0) {
index = - index - 1;
if (index < 0 || index > len) {
return 0;
}
}
return index;
}
public static int unique(int[] arr) {
if (arr.length == 1) return 1;
int len = 1;
while (len < arr.length && arr[len] != arr[len-1]) {
len++;
}
for (int i = len + 1; i < arr.length; i++) {
if (arr[i] != arr[len - 1]) {
len++;
arr[len - 1] = arr[i];
}
}
return len;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int[] a = new int[n];
int[] c = new int[n];
for (int i = 0; i < n; i++) {
int item = Integer.parseInt(st.nextToken());
c[i] = a[i] = item;
}
Arrays.sort(c);
nn = unique(c);
Node[] nodes = new Node[n];
for (int i = 0; i < n; i++) {
int l = lowerBound(c, nn, a[i]-k);
int r = upperBound(c, nn, a[i]+k);
int h = lowerBound(c, nn, a[i]);
nodes[i] = new Node(l, r, h);
}
st = new StringTokenizer(br.readLine());
int q = Integer.parseInt(st.nextToken());
B[] b = new B[q];
block = (int) Math.max(1.0, Math.sqrt((double)(n)*n/Math.max(1, q)));
for (int i = 0; i < q; i++) {
st = new StringTokenizer(br.readLine());
b[i] = new B();
b[i].id = i;
b[i].l = Integer.parseInt(st.nextToken());
b[i].r = Integer.parseInt(st.nextToken()) + 1;
}
Arrays.sort(b);
int l = 0;
int r = 0;
fenwick = new int[n];
long[] result = new long[q];
for (int i = 0; i < q; i++) {
while (l < b[i].l) {
nodes[l++].remove();
}
while (b[i].l < l) {
nodes[--l].add();
}
while (b[i].r < r) {
nodes[--r].remove();
}
while (r < b[i].r) {
nodes[r++].add();
}
result[b[i].id] = cnt;
}
for (int i = 0; i < result.length; i++) {
bw.write(String.valueOf(result[i]));
if (i != result.length - 1) {
bw.write("\n");
}
}
bw.newLine();
bw.close();
br.close();
}
}
In Python3 :
def clean():
put=input()
put=put.split(" ")
for i in range(len(put)):
put[i]=int(put[i])
return put
dict=dict()
def calc(l,u):
if(u==l):
return 0
global hgt,k,dict
if (l,u) in dict.keys():
return dict[(l,u)]
sum=0
for i in range(l,u):
if(abs(hgt[u]-hgt[i])<=k):
sum+=1
dict[(l,u)]=sum+calc(l,u-1)
return dict[(l,u)];
put=clean()
n=put[0]#number of wlers
k=put[1]#h diff
hgt=clean()
q=int(input())
for xyz in range(q):
put=clean()
l=put[0]
u=put[1]
print(str(calc(l,u)))
View More Similar Problems
Array-DS
An array is a type of data structure that stores elements of the same type in a contiguous block of memory. In an array, A, of size N, each memory location has some unique index, i (where 0<=i<N), that can be referenced as A[i] or Ai. Reverse an array of integers. Note: If you've already solved our C++ domain's Arrays Introduction challenge, you may want to skip this. Example: A=[1,2,3
View Solution →2D Array-DS
Given a 6*6 2D Array, arr: 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 An hourglass in A is a subset of values with indices falling in this pattern in arr's graphical representation: a b c d e f g There are 16 hourglasses in arr. An hourglass sum is the sum of an hourglass' values. Calculate the hourglass sum for every hourglass in arr, then print t
View Solution →Dynamic Array
Create a list, seqList, of n empty sequences, where each sequence is indexed from 0 to n-1. The elements within each of the n sequences also use 0-indexing. Create an integer, lastAnswer, and initialize it to 0. There are 2 types of queries that can be performed on the list of sequences: 1. Query: 1 x y a. Find the sequence, seq, at index ((x xor lastAnswer)%n) in seqList.
View Solution →Left Rotation
A left rotation operation on an array of size n shifts each of the array's elements 1 unit to the left. Given an integer, d, rotate the array that many steps left and return the result. Example: d=2 arr=[1,2,3,4,5] After 2 rotations, arr'=[3,4,5,1,2]. Function Description: Complete the rotateLeft function in the editor below. rotateLeft has the following parameters: 1. int d
View Solution →Sparse Arrays
There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings. Return an array of the results. Example: strings=['ab', 'ab', 'abc'] queries=['ab', 'abc', 'bc'] There are instances of 'ab', 1 of 'abc' and 0 of 'bc'. For each query, add an element to the return array, results=[2,1,0]. Fun
View Solution →Array Manipulation
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array. Example: n=10 queries=[[1,5,3], [4,8,7], [6,9,1]] Queries are interpreted as follows: a b k 1 5 3 4 8 7 6 9 1 Add the valu
View Solution →