Easy solution using stack


#1

Basic idea is that if the current domino can be merged with a domino from stack (contains dominoes to the right), then answer will also contain the dominoes dropped by stack domino.

CODE:
struct info
{
int s, f, in;
};

bool comp (info x, info y)
{
return x.s < y.s;
}

vector Solution::solve(vector &A, vector &B) {
int n = A.size();
info arr[n];
for (int i = 0; i < n; i++)
{
arr[i].s = A[i];
arr[i].f = A[i]+B[i]-1;
arr[i].in = i;
}
sort (arr, arr+n, comp);

vector <int> ans;
ans.resize(n);
stack <int> s;
for (int i = n-1; i >= 0; i--)
{
    ans[arr[i].in] = 1;
    while (!s.empty() && arr[i].f >= arr[s.top()].s)
    {
        ans[arr[i].in] += ans[arr[s.top()].in];
        s.pop();
    }
    s.push(i);
}

return ans;

}