Wet Mud

    1#include <bits/stdc++.h>
    2 
    3using namespace std;
    4 
    5const int INF = 1e9 + 7;
    6 
    7int main(){
    8    ios::sync_with_stdio(0);
    9    cin.tie(0);
    10    int n, m, j;
    11    cin >> n >> m >> j;
    12    vector<int> dry(n + 2, INF);
    13    dry[0] = dry[n + 1] = 0; 
    14    for (int i = 0; i < m; i++){
    15        int p, t; cin >> p >> t;
    16        dry[p] = t;
    17    }
    18    vector<int> v(n + 2, INF);
    19    v[0] = 0;
    20    deque<int> dq;
    21    dq.push_back(0);
    22    for (int i = 1; i <= n + 1; i++){
    23        while (!dq.empty() && dq.front() < i - j) dq.pop_front();
    24        if (dry[i] == INF || dq.empty()){
    25            v[i] = INF;
    26        }else {
    27            int best = v[dq.front()];
    28            if (best == INF) v[i] = INF;
    29            else v[i] = max(best, dry[i]);
    30        }
    31        if (v[i] != INF) {
    32            while (!dq.empty() && v[dq.back()] >= v[i]) dq.pop_back();
    33            dq.push_back(i);
    34        }
    35    }
    36        if (v[n + 1] == INF) cout << -1 << '\n';
    37        else cout << v[n + 1] << '\n';
    38        return 0;
    39}