COW3C-EDITORIAL

PROBLEM LINK: CodeChef: Practical coding for everyone

Practice

Contest

Author: Kushagra Kinger

Tester: Kushagra Kinger

Editorialist: Kushagra Kinger

DIFFICULTY:

SIMPLE

PREREQUISITES:

Basic Sweep Line.

PROBLEM:

A train is travelling on coordinate axis , collecting and dropping passengers at some coordinates . Find the sum of passengers present in the train at each mile over the whole journey.

QUICK EXPLANATION:

Keep a count of passengers present in the train at any moment , traverse the part of coordinate axis in which the train can have passengers, and keep adding the count to the answer.

EXPLANATION:

Basic Sweep Line Algorithm . Just traverse the whole x-axis from the mile at which the first passenger boards to the mile at which the last passenger departs. Keep a counter cnt which is the number of passengers in the train at the present coordinate. While updating cnt keep in mind that you add the number of passengers boarding at that mile (start[i]) to cnt , add cnt to ans and then subtract the number of passengers departing at that mile (end[i]) , so that both are considered for calculation of infection degree at that mile/coordinate.

Now how to keep track of the number of passengers in the train at a specific mile ? Maintain two arrays start and end where start[i] denotes the number of passengers boarding at the ith mile and end[i] denotes the number of passengers departing at that mile. Since the coordinates can be negative also , add a same positive number to all coordinates so that they become positive and can be mapped in an array.

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define mo 1000000007
typedef long long ll;
ll start[1000001]={0};
ll end[1000001]={0};
int main()
{
io
ll n;
cin>>n;
int ma=-1;
while(n--)
{
	int b,d;
	cin>>b>>d;
	b+=500000;
	d+=500000;
    start[b]++;
	end[d]++;
    ma=max(ma,d);
}
ll ans=0; // final answer
ll c=0;  // current number of passengers in the train
for(int i=0;i<=ma;i++)
{
    c+=start[i];
    ans=(ans+c)%mo;
    c-=end[i];
}
cout<<ans;

return 0;}

Here one can see that the contribution of a ith traveller is equal to end[i] - start[i] + 1. So sum up answers of all the travellers and it will be equivalent to ans calculated by this above mentioned approach.

Of Course, this a valid observation, Sweep Line is just used to explain in a simpler way.