All Tracks Data Structures Advanced Data Structures Fenwick (Binary Indexed) Trees Problem

Sherlock and Robots
Tag(s):

Medium

Problem
Editorial
Analytics

Sherlock is given a 1D array containing characteristics of $$N$$ robots on his birthday by Watson. Each robot has two special properties- Humour and Intelligence. For every robot, Sherlock has to calculate Personality Index. It is calculated as-

for i=1 to i=n 
 for j=i to j=n
   if(Humour[i]<=Humour[j])
    PersonalityIndex[i]+=(Intelligence[i]-Intelligence[j]);
    else
    PersonalityIndex[i]+=(Intelligence[j]-Intelligence[i]);
For every robot, print it's Personality Index in a new line.

Input Format
The first line contains $$N$$, the number of robots. Each of the next $$N$$ lines contains two integers- Humour and Intelligence.

Constraints

  • $$1 \le N \le 3*10^5 $$
  • $$1 \le Humour \le 3*10^5 $$
  • $$1 \le Intelligence \le 3*10^5 $$

Output Format
Output the Personality Index of every robot in a new line.

SAMPLE INPUT
4
4 5
1 3
2 3
3 1
SAMPLE OUTPUT
-8
2
2
0
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

School of Engineering, CUSAT

Challenge Name

221B Baker Street: Code for Watson

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications