PROBLEM LINK: CodeChef: Practical coding for everyone
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;}