You are not logged in. Please login at www.codechef.com to post your questions!

×

Problem of the day 2

Statement

You are observing the traffic in front of your house for $N$ seconds now. You have noted down your observations. Each car starts with some initial speed $U_i$ with some constant acceleration $A_i$ at the $L_i$th second and stops in the $R_i$th second. The $\text{total speed}$ at some particular second is the sum of all the speeds of cars at that particular second. Note that cars may start with any $U$ and stop in any $V$ abruptly. For each second from $1$ to $N$, calculate the total speed for each second. Acceleration is constant but the curve isn't smooth, i.e, the speed increases abruptly at the start of a second and remains the same throughout the second.

Input Format

The first line of input will contain and integer $N$ and $M$, denoting the number of seconds and number of cars respectively. Likes $2$ to $N+1$ each contain $U_i$ $A_i$ $L_i$ $R_i$ in the same order given denoting the initial speed, accelration per second(Increase in speed per second), start time and stop time for the $i$th.

Output Format

Print $N$ integers where the $i$th integer contains the $\text{total speed}$ in the $i$th second.

Constraints

$1 \leq N \leq 10^6 $
$1 \leq M \leq 10^5 $
$1 \leq U_i, A_i, L_i, R_i \leq 10^9 $

Example

Input:
10 3
1 1 1 10
2 2 1 3
1 3 5 7

Output: 3 6 9 4 6 10 14 8 9 10

Solution Explanation

We can use the idea of "Prefix Sums" here. What we did in prefix sums is store the sum till i in an array and find the sum of a subsegment. Here, we can do something uncannily similar: In another array, we store the change in the variable we need.

First lets solve a easier version of this problem to get a better hold of what I am talking about:
Given an array of size $N$, and $Q$ number of queries where each query gives a $L$, $R$ and $Val$, you need to increase all the elements from index $L$ to $R$ with the value $Val$, and in the end after all queries are executed, print all the elements.

The $O(NQ)$ solution is pretty trivial here and is just an implementation task but there is a $O(N+Q)$ solution. Take another array, lets call it $C$. For any $L$ and $R$ you need to you need to add $Val$ to $C[L]$ and subtract $Val$ from $C[R+1]$. You may still wonder why. Lets take an example.

Suppose I give you an array of $6$ elements initially all $0$ and then I do one query where $L = 2, R = 4, Val = 2$. So out array will become $$C = \{0, 2, 0, 0, -2, 0\}$$But whats the point?! The point is that, now if we take a variable and traverse this array, we get the elements! Lets take a variable say $X$ and we take a loop from $1$ to $6$ and we do this: $$X += C[i]$$ and also print X in each iteration. What will be the output? Wont it be $0, 2, 2, 2, 0, 0$? And isn't that exactly what we wanted? Why does this happen? This is because we add 2 in position 2 and then subtract 2 in position 5 to $X$. You can try doing more queries and dry run this logic to get the result everytime.

Now coming to the original problem, we can do the same thing that we wanted here but in this case we will need two arrays, one to keep track of the change in total speed and one to keep track of change in total acceleration(Does "total acceleration" make sense here?). In the speed array(say $V$), we will add $U_i$ to position $L_i$ and subtract $U_i+A_i \times (R_i-L_i)$ from position $R_i+1$. In the acceleration array(say $A$), we will add $A_i$ to position $L_i$ and subtract $A_i$ from position $R_i+1$. We will need two variables $Total\_speed$ and $Total\_acceleration$ to keep track of my total speed and acceleration in the current iteration and then do the following to change it according to our problem $$Total\_speed += V[i]+Total\_acceleration$$ $$Total\_acceleration += A[i]$$ And then just print $Total\_speed$ to get the desired result.

I hope you liked this problem. :)

If you have any kind of doubts, you can ask here in the comments or you can discuss with others in the WhatsApp group. Do not be shy, we ARE supposed to help each other learn.

asked 18 Oct '17, 00:37

ista2000's gravatar image

2★ista2000 ♦
2.3k419
accept rate: 20%

edited 30 Oct '17, 18:54


include <iostream>

using namespace std;

int main() { double Total_Speed,Total_Acceleration; int U[10],A[10],L[10],R[10]; int i=0; double N; int V[10]; double M; int C[10]; double Val; cin>>N>>M; while(i<m) {="" cin="">>U[i]>>A[i]>>R[i]>>L[i]; i++; } while(i<N) { V[i]=U[i]+A[i]*(L[i]-R[i]); Total_Speed+=V[i]+Total_Acceleration; Total_Acceleration+=A[i];
} while(i<N) { cout<<Total_Speed<<' '; } return 0; }

link

answered 01 Nov '17, 20:52

f0rl0rn2k's gravatar image

0★f0rl0rn2k
1
accept rate: 0%

this is my code guys can you please help me ... its exceeding the time limit

link

answered 01 Nov '17, 20:53

f0rl0rn2k's gravatar image

0★f0rl0rn2k
1
accept rate: 0%

So...in your code I see you took the array limits to be 10, what if m=450, Then the code does not run properly. Please take the array length as x[m]. after you input n and m. Also, using cin and cout is relatively slower than using printf and scanf. You can check how to use them online.

link

answered 01 Nov '17, 21:46

ryanmeatloaf's gravatar image

0★ryanmeatloaf
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×538

question asked: 18 Oct '17, 00:37

question was seen: 188 times

last updated: 01 Nov '17, 21:46

Related questions