Submission #1103890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103890		Pacybwoah	Escape Route 2 (JOI24_escape2)	C++17	54 / 100	3069 ms	73092 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){
        ll mini = inf;
        for(int times = 0; times < sz[pos]; times++){
            int id = pre[pos - 1] + times + 1;
            ll ans = 0;
            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";
                }
            }
            mini = min(mini, ans);
        }
        return mini;
    };
    auto pquery = [&](int pos, int kk){
        ll mini = inf;
        for(int times = 0; times < sz[pos]; times++){
            int id = pre[pos - 1] + times + 1;
            ll ans = 0;
            int k = kk;
            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;
    };
    int q;
    cin >> q;
    while(q--){
        int l, r;
        cin >> l >> r;
        cout << nquery(l, r - l) << "\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

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:92:10: warning: variable 'pquery' set but not used [-Wunused-but-set-variable]
   92 |     auto pquery = [&](int pos, int kk){
      |          ^~~~~~

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