CFR 635 E. Package Delivery ( Greedy + Stack Monotonicity )

Problem - E - Codeforces
Basically when the car is in gas station i, there is one and only one optimal decision.
If it is possible to move to the first station with cheaper gas price after this one, buy the minimum amount of gas here in order to move to that station. And if it is not possible to move to such station with cheaper gas price, buy all gas here until it is full, and move to the next nearest station. It is clear that we will not drop the optimal answer with this greedy strategy. For the start position, insert a station on pos 0 having infinite price, and for the end, insert a station on pos d having 0 price. This way, we will not have to take care of special cases. The technique used to pre-calculate the first_next_cheaper_position array, is making use of monotonicity where we run the loop backwards and keep it monotonically increasing by price.
Note: I messed up the station index with their real position when performing stack optimization and lost time Orz

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXD = 1e9 + 2;
const int MAXN = 1e9 + 2;
const int MAXM = 2e5 + 2;
const int MAXX = MAXD;
const int MAXP = 1e6 + 2;

int d, n, m;
pii station[ MAXM ];

int nxt[ MAXM ];
void preCalNext(){
    vector<pii> stk;
    for(int i = m - 1; i >= 0; --i){
        while( !stk.empty() && stk.back().second >= station[ i ].second )
            stk.pop_back(); // keeps only more expensive
        if( stk.empty() ) nxt[ i ] = -1; // no cheaper next
        else nxt[ i ] = stk.back().first; // it's sure the first cheaper next
        stk.push_back( pii( i, station[ i ].second ) );
    }
}

void solve(){
    sort( station, station + m );
    preCalNext();
    int pos = 0; // now on which station
    ll ans = 0LL, cur_gas = n;
    while( pos < m - 1 ){
        if( station[ pos + 1 ].first - station[ pos ].first > n ){
            cout << -1 << endl;
            return; // can't reach the next nearest station even full
        }
        if( nxt[ pos ] == -1 || station[ nxt[ pos ] ].first - station[ pos ].first > n ){
            ll dis = station[ pos + 1 ].first - station[ pos ].first;
            ans += (ll)( n - cur_gas ) * station[ pos ].second;
            cur_gas = n - dis;
            ++pos;
        } else{
            ll dis = station[ nxt[ pos ] ].first - station[ pos ].first;
            ans += max<ll>( dis - cur_gas, 0LL ) * station[ pos ].second;
            cur_gas = max<ll>( cur_gas - dis, 0LL );
            pos = nxt[ pos ];
        }
    }
    cout << ans << endl;
}

int main(){
    ios::sync_with_stdio( false );
    cin >> d >> n >> m;
    for(int i = 1; i <= m; ++i)
        cin >> station[ i ].first >> station[ i ].second;
    station[ 0 ] = pii( 0, 1e9 );
    station[ m + 1 ] = pii( d, 0 );
    m += 2;
    solve();
    return 0;
}