Submission #1150580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150580		Zero_OP	Escape Route 2 (JOI24_escape2)	C++20	23 / 100	256 ms	38088 KiB

Main

#include <bits/stdc++.h>

using namespace std;

//loops (warning : long long)
#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r - 1); i >= l; --i)

//pairs, tuples
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

//vectors
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sum_of(v) accumulate(all(v), 0ll)
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))

//binary search
#define lwb lower_bound
#define upb upper_bound

//other stuffs
#define dbg(x) "[" #x " = " << (x) << "]"
#define file(task) if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }

template<typename T>
bool minimize(T& a, const T& b){
    if(a > b) return a = b, true;
    return false;
}

template<typename T>
bool maximize(T& a, const T& b){
    if(a < b) return a = b, true;
    return false;
}

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using db = double;
using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vpi = vector<pi>;
using vpl = vector<pl>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAX = 1e5 + 5;
const int B = 350;
const ll inf = 1e18;

int N, T, idx[MAX];
int lift[20][MAX];
ll cost[20][MAX];
vpi flights[MAX];
pi f[MAX];
vi pos[MAX];
vl calc[MAX];
ll dp[MAX];
bool is_heavy[MAX];

bool cmp(const pi& a, const pi& b){
    if(a.ff == b.ff) return a.ff > b.ff;
    else return a.ff < b.ff;
}

ll jump_cost(int i, int k){
//    cout << dbg(i) << dbg(k) << '\n';
    ll sum = 0;
    while(k > 0){
        int b = 31 - __builtin_clz(k & (-k));
        sum += cost[b][i];
//        cout << dbg(b) << dbg(i) << '\n';
        i = lift[b][i];
        k ^= (1 << b);
    }
    sum += f[i].ss - f[i].ff;
    return sum;
}

void testcase(int ntestcase){
    cin >> N >> T;
    int cnt = 0;

    FOR(i, 0, N-1){
        int M;
        cin >> M;
        flights[i].resize(M);
        pos[i].resize(M);

        int prev = cnt;
        FOR(j, 0, M){
            cin >> flights[i][j].ff >> flights[i][j].ss;
            f[cnt] = flights[i][j];
            idx[cnt++] = i;
            pos[i][j] = cnt-1;
        }

        sort(all(flights[i]), cmp);
        if(i > 0){
            int ptr = 0;
            bool stop = false;
            FOR(j, 0, sz(flights[i-1])){
                int a, b; tie(a, b) = flights[i-1][j];

                if(stop){
                    lift[0][pos[i-1][j]] = pos[i][0];
                    cost[0][pos[i-1][j]] = T - a + flights[i][0].ff;
                } else{
                    while(ptr < sz(flights[i]) && b > flights[i][ptr].ff) ++ptr;
                    if(ptr == sz(flights[i])){
                        stop = true;
                        lift[0][pos[i-1][j]] = pos[i][0];
                        cost[0][pos[i-1][j]] = T - a + flights[i][0].ff;
                    } else {
                        lift[0][pos[i-1][j]] = pos[i][ptr];
                        cost[0][pos[i-1][j]] = flights[i][ptr].ff - a;
                    }
                }
            }
        }

        //comparing (A[i], B[i]) and (A[j], B[j])
        //(A[i], B[i]) is a bad flight if A[i] < A[j] && B[i] > B[j]
        if(M > B){
            is_heavy[i] = true;
            calc[i].resize(N-i, inf);
        }
    }

    pos[N-1].pb(cnt);
    idx[cnt++] = N-1;
    FOR(i, 0, sz(flights[N-2])){
        lift[0][pos[N-2][i]] = cnt-1;
        cost[0][pos[N-2][i]] = flights[N-2][i].ss - flights[N-2][i].ff;
    }

    lift[0][cnt-1] = cnt-1;
    cost[0][cnt-1] = 0;

    for(int i = 1; (1 << i) < N; ++i){
        for(int j = 0; j + (1 << i) < N; ++j){
            lift[i][j] = lift[i-1][lift[i-1][j]];
            cost[i][j] = cost[i-1][j] + cost[i-1][lift[i-1][j]];
        }
    }

//    for(int i = 0; (1 << i) <= N; ++i){
//        for(int j = 0; j + (1 << i) < N; ++j){
//            cout << dbg(i) << dbg(j) << dbg(lift[i][j]) << dbg(cost[i][j]) << '\n';
//        }
//    }

    FOR(i, 0, N-1) if(is_heavy[i]){
        fill(dp, dp+cnt, inf);

        FOR(k, 0, sz(flights[i])) dp[pos[i][k]] = 0;
        FOR(j, i, N-1){
            FOR(k, 0, sz(flights[j])){
                int p = pos[j][k];
                minimize(calc[i][j+1 - i], dp[p] + f[p].ss - f[p].ff);
                minimize(dp[lift[0][p]], dp[p] + cost[0][p]);
            }
        }
    }

//    FOR(i, 0, N-1){
//        cout << i << " ::: ";
//        FOR(j, 0, sz(flights[i])) cout << pos[i][j] << ' ';
//        cout << '\n';
//    }
//
//    FOR(i, 0, N-1){
//        cout << "Adfas: " << i << '\n';
//        FOR(j, 0, sz(flights[i])){
//            cout << pos[i][j] << " : " << lift[0][pos[i][j]] << ' ' << cost[0][pos[i][j]] << '\n';
//        } cout << '\n';
//    }

    int Q; cin >> Q;
    while(Q--){
        int l, r;
        cin >> l >> r;
        --l, --r;

        if(is_heavy[l]){
            cout << calc[l][r-l] << '\n';
        } else{
            ll result = inf;
            FOR(i, 0, sz(flights[l])){
                minimize(result, jump_cost(pos[l][i], r - l - 1));
            }
            cout << result << '\n';
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int T = 1;
//    cin >> T;
    FOR(i, 0, T) testcase(i);

    return 0;
}

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