About the Problem
| Setter(s) | Divyansh Verma, Vichitr Gandas |
| Tester(s) | Aswin Ashok |
| Difficulty | Easy |
| Topics | Binary Search, Observations |
| Practice | Link |
| Contest | Link |
Solution Idea
Idea is to use binary search. If two persons reach at destination in time t , that means they definitely meet at the destination. Hence just find maximum of energies of persons who reach the destination in time t . Now the max final energy would be x*max(e_i) if there are x persons. Now sort all the person’s energy based on the time they will take to reach the destination and then calculate prefix maximums. Now for each query binary search based on time and lets say x people reach the destination in given time t, then maximum energy would be prefixMax[x-1] considering 0-based indexing. Hence final energy would be x \times prefixMax[x-1].
Complexity Analysis:
- Time Complexity: O((k+q)logk)
- Space Complexity: O(k)
Codes
Setter's Code
/***************************************************
@author: vichitr
Compiled On: 21 Mar 2021
*****************************************************/
#include<bits/stdc++.h>
#define MAX 9223372036854775807
#define endl "\n"
#define ll long long
#define int long long
// #define double long double
#define pb push_back
#define pf pop_front
#define mp make_pair
#define ip pair<int, int>
#define F first
#define S second
#define loop(i,n) for(int i=0;i<n;i++)
#define loops(i,s,n) for(int i=s;i<=n;i++)
#define fast ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_updat
// using namespace __gnu_pbds;
// typedef tree<ip, null_type, less_equal<ip>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// order_of_key (k) : Number of items strictly smaller than k .
// find_by_order(k) : K-th element in a set (counting from zero).
const ll MOD = 1e9+7;
const ll SZ = 107;
const ll N = 1e5+7;
void solve(){
int n,m,k; cin>>n>>m>>k;
int e[k], x[k], y[k];
for(int i=0;i<k;i++)
cin>>e[i]>>x[i]>>y[i];
vector<pair<int, int>> v;
for(int i=0;i<k;i++){
int d = abs(n-x[i]) + abs(m-y[i]);
v.pb({d, e[i]});
}
sort(v.begin(), v.end());
int emax[k];
emax[0] = v[0].second;
for(int i=1;i<k;i++){
emax[i] = max(emax[i-1], v[i].second);
}
int q; cin>>q;
while(q--){
int t; cin>>t;
auto it = lower_bound(v.begin(), v.end(), mp(t+1, 0ll));
if(it == v.begin()){
cout<<"0\n";
continue;
}
it--;
int idx = it - v.begin();
int ans = (idx+1) * emax[idx];
cout<<ans<<'\n';
}
}
signed main()
{
fast;
int t=1;
cin >>t;
for(int i=1;i<=t;i++)
{
solve();
}
return 0;
}
Tester's Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
ll n,m,k;
cin>>n>>m>>k;
vector< pair<ll,ll> > v;
vector<ll> maxe,times;
for(int i=0;i<k;++i)
{
ll e,x,y;
cin>>e>>x>>y;
ll dist = abs(n-x)+abs(m-y);
v.push_back({dist,e});
}
sort(v.begin(),v.end());
for(pair<ll,ll> p: v)
maxe.push_back(p.second);
for(int i=1;i<maxe.size();++i)
maxe[i]=max(maxe[i-1],maxe[i]);
ll q;
cin>>q;
while(q--)
{
ll time;
cin>>time;
ll count = 0;
vector< pair<ll,ll> >::iterator pos = upper_bound(v.begin(),v.end(),make_pair(time,LLONG_MAX));
if(pos!=v.begin())
{
pos--;
count = pos - v.begin() + 1;
}
cout<<count*maxe[count-1]<<endl;
}
return;
}
int main()
{
int t;
cin>>t;
while(t--)
solve();
}
If you have used any other approach, share your approach in comments!
If you have any doubts, ask them in comments!