PROBLEM LINK:
Author: Ishika Chowdhury
Testers: Anupam Kumar Singh, CHILUKURI SRI HARSHA
Editorialist: Ishika Chowdhury
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Priority Queue or Multiset
PROBLEM:
The imposter is practicing hard to increase his speed so he decided to run for T seconds.
The first speed gets unlocked at 0^{th} second ( t_{i} = 0 sec ) and is valid upto time T ( t_{f} = T sec ).
For the next N - 1 speed, you are given S, t_{i} and t_{f} where t_{i} denotes the time at which speed S gets unlocked and t_{f} denotes that speed S is valid for upto time t_{f} after getting unlocked.
The impostor can run with any of the unlocked speed which is available at that time.
Find the maximum distance travelled by the impostor for the total duration of T seconds?
QUICK EXPLANATION:
The imposter will start running at t_{i} = 0 sec and will continue to run for a total of T seconds.
His target is to calculate the maximum distance covered. So more the speed , more will be the distance covered in T seconds
EXPLANATION:
We can use a Priority Queue to store unlocked speeds so that the maximum of unlocked speeds will be always at top. We are using map of vectors which is taking start time as key and its values are - the speeds getting unlocked at that particular start time and its end time. Since the first speed gets unlocked at 0 sec and is valid upto T seconds, it will never be popped out of the priority queue pq.
The imposter will start running till a new speed gets unlocked first. If more than 1 speed gets unlocked at the same time, he will choose the maximum speed sp which we are calculating using a priority queue pq and will be valid till another speed gets unlocked(ie, the next initial time).
So 3 cases will arise :
Case 1 : If the final time t_{f} of that particular speed sp is less than or equal to the time travelled till now (tc), then that speed's validation is over. Since it is of no use , we will pop it out.
Case 2 : If the final time t_{f} of that particular speed sp is greater than or equal to the next initial time, then the imposter will travel till the next initial time and dist = (next initial time - tc) * sp. So total time travelled till now will be -----
tc = next initial time.
Now we look for next maximum speed getting unlocked.
Case 3 : If the final time t_f of that particular speed sp is less than the next initial time, then the imposter will travel till t_f and dist = (next initial time - t_f )* sp. So total time travelled till now will be ------
tc = t_f and that speed will be popped out since its validation is over.
We will continue to run these cases till total time covered is T, i.e., next initial time for unlocking is T secs.
Time Complexity:
The time complexity is O( TC * N( log N )) , TC : number of test cases.
Solution:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
typedef long long int ll;
int main()
{
fast;
int t;
cin>>t;
while(t--)
{
ll n;
cin >> n;
ll s,l,T;
cin >> s >> l >> T;
ll tc = 0; //counts current time travelled
ll dist = 0; // counts how much total dist travelled in time tc
map <ll, vector<pair<ll,ll> > > mp; // key = start time and value = { speed , end time }
for( ll i = 1; i < n; i++ )
{
ll S , r;
cin >> S >> l >> r;
mp[l].push_back({S,r});
}
mp[T].push_back({0,0});
priority_queue<pair< ll , ll> > pq;
pq.push({ s , T });
map <ll, vector<pair<ll,ll> > > :: iterator it;
for( it = mp.begin();it!=mp.end();it++ )
{
ll next_initial_time = it->first;
//total time travelled till now is stored in tc
while(tc < next_initial_time && !pq.empty())
{
ll sp = pq.top().first;
ll tf = pq.top().second;
if (tf <= tc )
pq.pop();
else if(tf >= next_initial_time)
{
ll x = (next_initial_time - tc );
tc = next_initial_time ;
dist += x * sp;
break;
}
else
{
//pop till we get a tf >= next_initial_time and update time tc
ll x = (tf - tc );
tc = tf;
dist += x * sp;
pq.pop();
}
}
for(int i = 0 ; i < mp[next_initial_time].size() ; i++)
pq.push({ mp[next_initial_time][i].first , mp[next_initial_time][i].second });
}
cout << dist << "\n";
}
}
Tester's Solution using Multisets
#include<bits/stdc++.h>
using ll = long long int;
using namespace std;
#define sync ios_base::sync_with_stdio(false); cin.tie(NULL)
#define F first
#define S second
const int N = 1e6 + 5;
int main()
{
sync;
int t;
cin >> t;
assert(1 <= t && t <= 100);
while(t--){
int n;
cin >> n;
assert(1 <= n && n <= 1e5);
vector <pair<ll, ll > > all;
for(int i = 0; i < n; i++){
ll s, l, r;
cin >> s >> l >> r;
assert(1 <= s && s <= 1e9 && 0 <= l && l <= 1e9 && 0 <= r && r <= 1e9);
all.push_back({l, s});
all.push_back({r, -s});
}
sort(all.begin(),all.end());
ll ans = 0;
ll curr = 0;
multiset<ll> speed;
int ix=0;
int allSize=all.size();
while(ix<allSize){
ll same_time = all[ix].F;
if(speed.size()){
auto it = speed.end();
it--;
ans += (*it) * (same_time - curr);
}
while(ix<all.size() && all[ix].F == same_time){
ll aux_sp = all[ix].S;
if(aux_sp < 0)
speed.erase(speed.lower_bound(-aux_sp));
else
speed.insert(aux_sp);
//all.erase(all.begin());
ix++;
}
curr = same_time;
}
cout << ans << '\n';
}
return 0;
}
Tester's Solution using Priority_Queue
#include<bits/stdc++.h>
using namespace std;
int SUM_N=0;
int run(){
int n,i,a,b,c,vi=0;
unsigned long long int solution=0;
cin>>n;
SUM_N+=n;
vector <pair<int,pair<int,int>>> v;
priority_queue <pair<int,int>> pq;
// managing initail case
cin>>a>>b>>c;
v.push_back({b,{a,c}});
int t=c;
for(i=0;i<n-1;i++){
cin>>a>>b>>c;
v.push_back({b,{a,c}});
}
// sorting vector wrt initial time
sort(v.begin(),v.end());
for(i=0;i<t;){
//add elements to priority queue at i=initial time of a speed
while(vi!=n and v[vi].first==i){
pq.push(v[vi++].second);
}
//remove elements from priority queue if i>=final time of a speed
while(!pq.empty() and pq.top().second<=i){
pq.pop();
}
// these three lines ensure not to go linearly upto t
// just skip upto next key value of i
// i.e min
// (next smallest initial value of non used speed (in vector)) and
// (the final time when pq.top() ends at)
int next_index=min(vi==n?t+1:v[vi].first,pq.top().second);
// we can add same speed for entire duration
solution+=(next_index-i)*1LL*(pq.empty()?0:pq.top().first);
i=next_index;
}
cout<<solution<<endl;
return 0;
}
int main(){
int t;
cin>>t;
while(t--){
run();
}
return 0;
}