Submission #1108690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108690		vladilius	Escape Route 2 (JOI24_escape2)	C++17	14 / 100	3070 ms	5960 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const ll inf = numeric_limits<ll> :: max();

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, D; cin>>n>>D;
    vector<int> x(n);
    vector<pii> t[n];
    for (int i = 1; i < n; i++){
        cin>>x[i];
        for (int j = 0; j < x[i]; j++){
            int a, b; cin>>a>>b;
            t[i].pb({a, b});
        }
    }
    
    for (int i = 1; i < n; i++){
        sort(t[i].begin(), t[i].end());
        vector<pii> nw;
        for (int j = 0; j < x[i]; j++){
            while (!nw.empty() && nw.back().ss >= t[i][j].ss){
                nw.pop_back();
            }
            if (nw.empty() || nw.back().ff != t[i][j].ff){
                nw.pb(t[i][j]);
            }
        }
        
        t[i] = nw;
        x[i] = (int) t[i].size();
    }
    
    vector<int> p(n);
    for (int i = 1; i < n; i++){
        p[i] = p[i - 1] + x[i];
    }
    int S = p.back();
    vector<int> g(S);
    vector<bool> e(S);
    for (int i = 1; i + 1 < n; i++){
        int k = x[i + 1] - 1, mn = 0;
        for (int j = x[i] - 1; j >= 0; j--){
            while (k >= 0 && t[i + 1][k].ff >= t[i][j].ss){
                mn = k--;
            }
            g[p[i - 1] + j] = p[i] + mn;
            e[p[i - 1] + j] = (t[i][j].ss > t[i + 1][mn].ff);
        }
    }
    
    auto get = [&](int l, int r){
        ll out = inf;
        for (int i = 0; i < x[l]; i++){
            int tt = r - l - 1, f = p[l - 1] + i, cc = 0;
            while (tt--){
                cc += e[f];
                f = g[f];
            }
            out = min(out, 1LL * D * cc + (t[r - 1][f - p[r - 2]].ss - t[l][i].ff));
        }
        return out;
    };
    
    int q; cin>>q;
    for (int i = 1; i <= q; i++){
        int l, r; cin>>l>>r;
        cout<<get(l, r)<<"\n";
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 0 / 17
• Subtask 4: 0 / 23
• Subtask 5: 0 / 36
• Subtask 6: 0 / 10