Grid Queries - Editorial

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)logn)
  • 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!

2 Likes

Can you make the test cases for the above problem visible, So that we debug our code.
Thanks

Hey we don’t make them public. And testcases are huge. You won’t be able to figure out by looking at them. If you need help, paste your code here, we can try helping!

1 Like

https://shar.es/ao9lh7
This is the code link, Can you tell where it fails

I took a look at your solution. It misses the fact that there can be multiple persons in the same square initially too. So, to include that too in the solution you will have to keep track of initial count in each cel as well as the mas energy person in that cell. Here is a modified version of your solution that does that - https://codedrills.io/submissions/34313

3 Likes