Submission #1130878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130878		fzyzzz_z	Escape Route 2 (JOI24_escape2)	C++20	14 / 100	3094 ms	4988 KiB

Main

#include<bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 1e5 + 10; 
const int L = 17;

int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(0); 
    
    int n; 
    ll t; 
    cin >> n >> t; 

    vector<vector<pair<int, int>>> a(n); 
    for (int i = 0; i < n - 1; ++i) {
        int m; 
        cin >> m; 
        a[i].resize(m); 
        for (auto & [x, y]: a[i]) {
            cin >> x >> y; 
        }
        sort(a[i].begin(), a[i].end()); 

        vector<pair<int, int>> b; 
        for (auto [x, y]: a[i]) {
            if (b.size() && b.back().first == x) continue; 
            while (b.size() && b.back().second >= y) b.pop_back(); 
            b.emplace_back(x, y); 
        }
        a[i] = b; 
    }

    int q; 
    cin >> q; 
    while (q--) {
        int l, r; 
        cin >> l >> r; 
        l--; r--; 
        ll ans = 1e18; 

        for (auto [x, y]: a[l]) {
            ll cur = 0; 
            int at = l; 
            while (at < r) {
                int ok = 0; 
                for (auto [t0, t1]: a[at]) {
                    if (t0 >= x) {
                        cur += t1 - x; 
                        x = t1; 
                        ok = 1; 
                        at++; 
                        break; 
                    }
                }
                if (ok) continue; 

                cur += t - x; 
                x = 0; 
            }
            ans = min(ans, cur); 
        }
        cout << ans << '\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