All Tracks Algorithms Searching Binary Search Problem

Timely Orders
Tag(s):

Binary Search, Data Structures, Easy

Problem
Editorial
Analytics

Today, you have been given a task like ones back end developers face on a daily basis. You need to help in dealing with large amount of requests received in a purchasing application. The application has the following properties:

  1. Consumers place large number of orders via this application

  2. Each request has a time stamp and an order size associated with it.

  3. Each order size is considered in terms of kilo-grams and can be of integer weight only.

Now, the data analytics team needs some information on regular intervals. Based on the requests received in the app, you need to help answer all queries posed by the data-analytics team. So, your task is:

Given $$2$$ types of queries, the first one being of the form $$1$$ $$X$$ $$T$$, indicates an order of weight $$X$$ is received at time $$T$$. The second one is of the form $$2$$ $$K$$ $$T$$ indicates that the data analytics team asks you about the summation of weight of the orders received during the last $$K$$ minutes at time $$T$$. The first query can be of the first type only.

For each query, it is guaranteed that they are given in ascending order of time. It means that given $$q$$ queries and each query having a time $$T$$ associated with it, $$ T_{i} < T_{i+1} < T_{i+2}... < T_q $$.

Input Format :

The first line contains a single integer $$q$$ denoting the total number of queries. Each of the next $$q$$ lines contains either of the two types of queries. Each query of type $$1$$ first starts with the number $$1$$ followed by $$2$$ integers $$X$$ and $$T$$. Each query of the second type first starts with the integer $$2$$ and is then followed by $$2$$ integers $$K$$ and $$T$$.

Output Format :

For each query of the second type, you need to print the required answer on a new line.

Constraints:

$$ 1 \le q \le 10^5 $$

$$ 1 \le T_{i} \le 10^9 $$ , $$\forall 1 \le i \le q $$

$$ 1 \le X_{i} \le 10^9 $$ , $$\forall 1 \le i \le q $$

$$ 1 \le K_{i} \le T_{i} $$ , $$\forall 1 \le i \le q $$

Note:

The first query can be of the first type only.

SAMPLE INPUT
4
1 20 3
1 40 4
2 5 5
1 100 100
SAMPLE OUTPUT
60
Explanation

Here, you first receive an order of weight $$20$$ at time $$3$$ , then an order of weight $$40$$ at time $$4$$. Now, for the third query, you need to find the summation of all orders received from time $$0$$ to time $$5$$, i.e $$20$$ + $$40$$ = $$60$$. Now you finally recieve another order at time $$100$$ , but are asked nothing about it.

Time Limit: 2.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++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Honeywell

Challenge Name

Honeywell Android Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications