/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 2ms 532.0 KiB
#3 Accepted 2ms 532.0 KiB
#4 Accepted 3ms 532.0 KiB
#5 Accepted 84ms 532.0 KiB
#6 Accepted 92ms 620.0 KiB
#7 Accepted 63ms 984.0 KiB
#8 Accepted 347ms 54.047 MiB
#9 Accepted 323ms 12.242 MiB
#10 Accepted 22ms 532.0 KiB
#11 Accepted 26ms 532.0 KiB
#12 Accepted 430ms 52.594 MiB
#13 Accepted 100ms 536.0 KiB
#14 Accepted 293ms 41.613 MiB
#15 Accepted 330ms 38.617 MiB

Code

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

static const long long NEG_INF = -(1LL << 60);

struct SegTree {
    int n;
    vector<long long> st;
    SegTree(int n): n(n), st(4*n, NEG_INF) {}

    void update(int idx, long long val, int p, int l, int r) {
        if (l == r) {
            st[p] = max(st[p], val);
            return;
        }
        int m = (l + r) >> 1;
        if (idx <= m) update(idx, val, p<<1, l, m);
        else update(idx, val, p<<1|1, m+1, r);
        st[p] = max(st[p<<1], st[p<<1|1]);
    }

    void update(int idx, long long val) {
        update(idx, val, 1, 0, n-1);
    }

    long long query(int ql, int qr, int p, int l, int r) {
        if (qr < l || r < ql) return NEG_INF;
        if (ql <= l && r <= qr) return st[p];
        int m = (l + r) >> 1;
        return max(query(ql, qr, p<<1, l, m),
                   query(ql, qr, p<<1|1, m+1, r));
    }

    long long query(int ql, int qr) {
        if (ql > qr) return NEG_INF;
        return query(ql, qr, 1, 0, n-1);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;

        vector<long long> A(n+1), C(n+1);
        for(int i = 1; i <= n; i++) cin >> A[i];
        for(int i = 1; i <= n; i++) cin >> C[i];

        if(n == 1){
            cout << 0 << '\n';
            continue;
        }

        vector<long long> S(n+1);
        S[0] = 0;
        for(int i = 1; i <= n; i++) S[i] = S[i-1] + A[i];

        vector<long long> coords;
        for(int i = 0; i <= n; i++) coords.push_back(S[i]);
        for(int j = 1; j <= n; j++) coords.push_back(S[j] - C[j]);

        sort(coords.begin(), coords.end());
        coords.erase(unique(coords.begin(), coords.end()), coords.end());

        auto get_id = [&](long long x){
            return int(lower_bound(coords.begin(), coords.end(), x) - coords.begin());
        };

        SegTree st(coords.size());

        vector<long long> dp(n+1, NEG_INF);

        // Base case: position 1 reachable with 0 moves
        dp[1] = 0;
        st.update(get_id(S[0]), dp[1]);

        for(int j = 2; j <= n; j++){
            long long limit = S[j] - C[j];
            int idx = upper_bound(coords.begin(), coords.end(), limit) - coords.begin() - 1;
            if(idx >= 0){
                long long best = st.query(0, idx);
                if(best != NEG_INF){
                    dp[j] = best + 1;
                    st.update(get_id(S[j-1]), dp[j]);
                }
            }
        }

        if(dp[n] < 0) cout << -1 << '\n';
        else cout << dp[n] << '\n';
    }

    return 0;
}

Information

Submit By
Type
Submission
Problem
P1199 F. Roy and Path Game
Language
C++17 (G++ 13.2.0)
Submit At
2026-01-06 17:56:19
Judged At
2026-01-06 17:56:19
Judged By
Score
100
Total Time
430ms
Peak Memory
54.047 MiB