Array Pairs


Problem Statement :


Consider an array of n  integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j)  pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i <  j.

Input Format

The first line contains an integer, n , denoting the number of elements in the array.
The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .


Solution :



title-img 


                            Solution in C :

In C++ :




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

#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define f first
#define s second
#define pi pair<ll,ll>
#define pii pair<pi,ll>
#define f first
#define s second
#define pb push_back
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)

int N;
int A[1000011];
int L[1000011];
int R[1000011];
vector<int>g[1000011];
ll bt[1000011];
int maxn;
void update(int ind, int val) {
    while(ind <= maxn) {
        bt[ind] += val;
        ind += (ind & -ind);
    }
}
ll query(int ind) {
    ll ans = 0;
    while(ind > 0) {
        ans += bt[ind];
        ind -= (ind & -ind);
    }
    return ans;
}
vector<int>V;
int find_ind(int x) {
    if(V.back() <= x) return V.size();
    return upper_bound(V.begin(), V.end(), x) - V.begin();
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    set<int>S;
    unordered_map<int, int>M;

    for(int i = 1; i <= N; i++) {
        cin >> A[i];
        assert(A[i] >= 1 and A[i] <= 1000000000);
        S.insert(A[i]);
    }
    vector<pi>window;
    for(int i = 1; i <= N; i++) {
        while(window.size() > 0 and window.back().f < A[i]) window.pop_back();
        if(window.size() == 0) L[i] = 1;
        else {
            L[i] = window.back().s + 1;
        }
        window.pb(mp(A[i], i));
    }
    window.clear();
    for(int i = N; i >= 1; i--) {
        while(window.size() > 0 and window.back().f <= A[i]) window.pop_back();
        if(window.size() == 0) R[i] = N;
        else {
            R[i] = window.back().s - 1;
        }
        window.pb(mp(A[i], i));
    }

    for(int i = 1; i <= N; i++) {
        if(i - L[i] <= R[i] - i) {
            for(int j = L[i]; j < i; j++) {
                g[i - 1].pb(-A[i] / A[j]);
                g[R[i]].pb(A[i] / A[j]);
                //S.insert(A[i]/A[j]);
            }

            g[i].pb(-1);
            g[R[i]].pb(1);
        } else {

            for(int j = i + 1; j <= R[i]; j++) {
                g[L[i] - 1].pb(-A[i] / A[j]);
                g[i].pb(A[i] / A[j]);
                //S.insert(A[i]/A[j]);
            }

            g[L[i] - 1].pb(-1);
            g[i - 1].pb(1);
        }
    }
    maxn = S.size() + 2;
    int cnt = 1;
    for(set<int>::iterator it = S.begin(); it != S.end(); it++) {
        M[*it] = cnt++;
    }
    ll ans = 0;
    int r;
    V = vector<int>(S.begin(), S.end());
    for(int i = 1; i <= N; i++) {
        update(M[A[i]], 1);
        for(int j = 0; j < g[i].size(); j++) {
            r = find_ind(abs(g[i][j]));
            if(g[i][j] < 0) {
                ans -= query(r);
            } else {
                ans += query(r);
            }
        }
    }
    cout << ans;
}








View More Similar Problems

Pair Sums

Given an array, we define its value to be the value obtained by following these instructions: Write down all pairs of numbers from this array. Compute the product of each pair. Find the sum of all the products. For example, for a given array, for a given array [7,2 ,-1 ,2 ] Note that ( 7 , 2 ) is listed twice, one for each occurrence of 2. Given an array of integers, find the largest v

View Solution →

Lazy White Falcon

White Falcon just solved the data structure problem below using heavy-light decomposition. Can you help her find a new solution that doesn't require implementing any fancy techniques? There are 2 types of query operations that can be performed on a tree: 1 u x: Assign x as the value of node u. 2 u v: Print the sum of the node values in the unique path from node u to node v. Given a tree wi

View Solution →

Ticket to Ride

Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game. There are n cities on the map and n - 1 road plans. Each road plan consists of the following: Two cities which can be directly connected by a road. The length of the proposed road. The entire road plan is designed in such a way that if o

View Solution →

Heavy Light White Falcon

Our lazy white falcon finally decided to learn heavy-light decomposition. Her teacher gave an assignment for her to practice this new technique. Please help her by solving this problem. You are given a tree with N nodes and each node's value is initially 0. The problem asks you to operate the following two types of queries: "1 u x" assign x to the value of the node . "2 u v" print the maxim

View Solution →

Number Game on a Tree

Andy and Lily love playing games with numbers and trees. Today they have a tree consisting of n nodes and n -1 edges. Each edge i has an integer weight, wi. Before the game starts, Andy chooses an unordered pair of distinct nodes, ( u , v ), and uses all the edge weights present on the unique path from node u to node v to construct a list of numbers. For example, in the diagram below, Andy

View Solution →

Heavy Light 2 White Falcon

White Falcon was amazed by what she can do with heavy-light decomposition on trees. As a resut, she wants to improve her expertise on heavy-light decomposition. Her teacher gave her an another assignment which requires path updates. As always, White Falcon needs your help with the assignment. You are given a tree with N nodes and each node's value Vi is initially 0. Let's denote the path fr

View Solution →