Submission #1103920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103920		Pacybwoah	Escape Route 2 (JOI24_escape2)	C++17	100 / 100	702 ms	90392 KiB

Main

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
const int K = 1000;
using namespace std;
typedef long long ll;
const ll inf = 8e18;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m = 0;
    ll t;
    cin >> n >> t;
    vector<vector<pair<int, int>>> rngs(n);
    vector<int> sz(n), pre(n);
    for(int i = 1; i < n; i++){
        int tmp;
        cin >> tmp;
        for(int j = 0; j < tmp; j++){
            int a, b;
            cin >> a >> b;
            rngs[i].emplace_back(a, b);
        }
        sort(rngs[i].begin(), rngs[i].end());
        vector<pair<int, int>> vtmp;
        int mini = 2e9;
        for(int j = tmp - 1; j >= 0; j--){
            auto x = rngs[i][j];
            if(x.second < mini){
                mini = x.second;
                vtmp.push_back(x);
            }
        }
        reverse(vtmp.begin(), vtmp.end());
        rngs[i] = vtmp;
        sz[i] = (int)rngs[i].size();
        m += sz[i];
        pre[i] = pre[i - 1] + sz[i];
    }
    vector<vector<pair<int, ll>>> panc(17, vector<pair<int, ll>>(m + 1)), nanc(17, vector<pair<int, ll>>(m + 1));
    vector<pair<int, ll>> lst(m + 1), nxt(m + 1);
    for(int i = 2; i < n; i++){
        int ptr = 0;
        for(int j = 0; j < sz[i - 1]; j++){
            int id = pre[i - 2] + j + 1;
            while(ptr < sz[i] && rngs[i][ptr].first < rngs[i - 1][j].second) ptr++;
            if(ptr < sz[i]) nxt[id] = make_pair(pre[i - 1] + ptr + 1, rngs[i][ptr].first - rngs[i - 1][j].second);
            else nxt[id] = make_pair(pre[i - 1] + 1, t + rngs[i][0].first - rngs[i - 1][j].second);
        }
        ptr = -1;
        for(int j = 0; j < sz[i]; j++){
            int id = pre[i - 1] + j + 1;
            while(ptr < sz[i - 1] - 1 && rngs[i - 1][ptr + 1].second <= rngs[i][j].first) ptr++;
            if(ptr >= 0) lst[id] = make_pair(pre[i - 2] + ptr + 1, rngs[i][j].first - rngs[i - 1][ptr].second);
            else lst[id] = make_pair(pre[i - 1], t + rngs[i][j].first - rngs[i - 1][sz[i - 1] - 1].second);
        }
    }
    for(int i = 1; i < n; i++){
        for(int j = 0; j < sz[i]; j++){
            int id = pre[i - 1] + j + 1;
            nanc[0][id] = make_pair(id, rngs[i][j].second - rngs[i][j].first);
            panc[0][id] = nanc[0][id];
        }
    }
    for(int i = 1; i < 17; i++){
        for(int j = 1; j <= m; j++){
            nanc[i][j] = make_pair(nanc[i - 1][nxt[nanc[i - 1][j].first].first].first, nanc[i - 1][j].second + nanc[i - 1][nxt[nanc[i - 1][j].first].first].second + nxt[nanc[i - 1][j].first].second);
            panc[i][j] = make_pair(panc[i - 1][lst[panc[i - 1][j].first].first].first, panc[i - 1][j].second + panc[i - 1][lst[panc[i - 1][j].first].first].second + lst[panc[i - 1][j].first].second);
        }
    }
    auto nquery = [&](int pos, int kk, int k2){
        ll mini = inf;
        for(int times = 0; times < sz[pos]; times++){
            int id = pre[pos - 1] + times + 1;
            ll ans = -rngs[pos][times].second + rngs[pos][times].first;
            int k = kk;
            for(int i = 0; i < 17; i++){
                if(k & (1 << i)){
                    k -= (1 << i);
                    ans += nanc[i][id].second;
                    id = nanc[i][id].first;
                    if(k > 0) ans += nxt[id].second;
                    id = nxt[id].first;
                    //cout << id << " " << ans << "\n";
                }
            }
            //cout << ans << "\n";
            id = pre[pos - 1] + times + 1;
            k = k2;
            for(int i = 0; i < 17; i++){
                if(k & (1 << i)){
                    k -= (1 << i);
                    ans += panc[i][id].second;
                    id = panc[i][id].first;
                    if(k > 0) ans += lst[id].second;
                    id = lst[id].first;
                }
            }
            mini = min(mini, ans);
        }
        return mini;
    };
    vector<vector<pair<int, int>>> st(17, vector<pair<int, int>>(n));
    for(int j = 1; j < n; j++){
        st[0][j] = make_pair(sz[j], j);
    }
    for(int i = 1; i < 17; i++) for(int j = 1; j < n; j++) st[i][j] = min(st[i - 1][j], st[i - 1][min(n - 1, j + (1 << (i - 1)))]);
    vector<int> bases(n);
    for(int i = 1; i < n; i++){
        bases[i] = bases[i - 1];
        if(i == (1 << (bases[i] + 1))) bases[i]++;
    }
    auto query = [&](int l, int r){
        r--;
        int len = r - l + 1;
        return min(st[bases[len]][l], st[bases[len]][r - (1 << bases[len]) + 1]).second;
    };
    int q;
    cin >> q;
    vector<ll> anss(q);
    vector<vector<pair<int, int>>> queries(n + 1);
    for(int i = 0; i < q; i++){
        int l, r;
        cin >> l >> r;
        if(r - l > K){
            int best = query(l, r);
            anss[i] = nquery(best, r - best, best - l + 1);
            //cout << best << "\n";
        }
        else{
            queries[l].emplace_back(r, i);
        }
    }
    ll mini = inf;
    for(int i = 1; i < n; i++){
        if(queries[i].empty()) continue;
        sort(queries[i].begin(), queries[i].end());
        int szz = queries[i].size();
        int ptr = 0;
        vector<ll> ans(sz[i]);
        vector<int> id(sz[i]);
        for(int j = 0; j < sz[i]; j++) id[j] = pre[i - 1] + j + 1;
        for(int j = i; j < min(n, i + K); j++){
            mini = inf;
            for(int k = 0; k < sz[i]; k++){
                ans[k] += nanc[0][id[k]].second;
                mini = min(mini, ans[k]);
            }
            while(ptr < szz && queries[i][ptr].first - 1 == j){
                anss[queries[i][ptr].second] = mini;
                ptr++;
            }
            for(int k = 0; k < sz[i]; k++){
                ans[k] += nxt[id[k]].second;
                id[k] = nxt[id[k]].first;
            }
        }
    }
    for(int i = 0; i < q; i++) cout << anss[i] << "\n";
    //for(int i = 1; i <= m; i++) cout << nanc[1][i].first << " " << nanc[1][i].second << '\n';
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run escape.cpp

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