2021 Shanghai match-h-two point answer

The main idea of the topic :

There is $n$ A car . Each car has coordinates , Speed ( There is a direction ), type . Ask you the earliest time when a car collides
$n\le 1e5$

Topic ideas :

Obviously, the two-point answer . The key is how to check Collision ?

No collision is equivalent to The relative position between any two pairs of different types of cars Nothing has changed .

such check Obviously right , But obviously the complexity is explosive .

But we only need to save the subscript of different types of cars closest to it on the left and the subscript of different types of cars closest to it on the right .

Two minutes later sort, then $O(n)$ Of check Whether each car meets the conditions .

Because once there is a collision , There must be a change in the left and right states of the car .
Or say : The relative position has not changed, which is equivalent to that the nearest two different cars around each car have not changed

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vll vector<ll>
#define fi first
#define se second
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
struct Node
{
    
    ll p , v , t , id;
    bool operator < (const Node & a){
    
        return p < a.p;
    }
}a[maxn] , b[maxn] , c[maxn];
int L[maxn] , R[maxn];
int main()
{
    
    ios::sync_with_stdio(false);
    int n , k; cin >> n >> k;
    for (int i = 1 ; i <= n ; i++){
    
        cin >> a[i].p >> a[i].v >> a[i].t;
        a[i].id = i;
    }
    sort(a + 1 , a + 1 + n);
    R[a[n].id] = -1;
    for (int i = n - 1 ; i >= 1 ; i--){
    
        if (a[i].t == a[i + 1].t){
    
            R[a[i].id] = R[a[i + 1].id];
        }else {
    
            R[a[i].id] = a[i + 1].id;
        }
    }
    L[a[1].id] = -1;
    for (int i = 2 ; i <= n ; i++){
    
        if (a[i].t == a[i - 1].t){
    
            L[a[i].id] = L[a[i - 1].id];
        }else {
    
            L[a[i].id] = a[i - 1].id;
        }
    }
    ll l = 1 , r = 3e9;
  // ll l = 1 , r = 1;
    while (l <= r){
    
        ll mid = l + r >> 1;
        for (int i = 1 ; i <= n ; i++){
    
            b[i] = a[i];
            b[i].p += mid * b[i].v;
        }
        sort(b + 1 , b + 1 + n);
        for (int i = 1 ; i <= n ; i++) c[b[i].id] = b[i];
        bool ok = true;
        for (int i = 1 ; i <= n ; i++){
    
            int pos = b[i].id;
            if (L[pos] != -1){
    
                if (c[L[pos]].p >= c[pos].p){
    
                    ok = false;
                    break;
                }
            }
            if (R[pos] != -1){
    
                if (c[R[pos]].p <= c[pos].p){
    
                    ok = false;
                    break;
                }
            }
        }
        if (ok) l = mid + 1;
        else r = mid - 1;
    }
    if (r == 3e9) cout << -1 << endl;
    else cout << r << endl;
    return 0;
}