/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 2ms 532.0 KiB
#3 Accepted 2ms 580.0 KiB
#4 Accepted 2ms 532.0 KiB
#5 Accepted 62ms 3.398 MiB
#6 Accepted 65ms 3.344 MiB
#7 Accepted 39ms 1.422 MiB
#8 Accepted 179ms 19.723 MiB
#9 Accepted 160ms 7.617 MiB
#10 Accepted 16ms 1.02 MiB
#11 Accepted 17ms 840.0 KiB
#12 Accepted 231ms 19.48 MiB
#13 Accepted 73ms 3.27 MiB
#14 Accepted 151ms 19.555 MiB
#15 Accepted 175ms 19.555 MiB

Code

/*
    JAI JAGANNATH!
*/
//@Author : zanj0

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <class T>
using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

// #define LOCAL  // ← enable locally via -DLOCAL; keep commented for OJ
#define ff first
#define ss second
#define pb push_back
#define MOD 1000000007
#define inf 1000000000000000000LL
#define ps(x, y) fixed << setprecision(y) << x
#define w(x)  \
    int x;    \
    cin >> x; \
    while (x--)
#define endl "\n"
#define timetaken cerr << "Time : " << 1000 * (long double)clock() / (long double)CLOCKS_PER_SEC << "ms\n"

typedef long long int lli;

#ifdef LOCAL
#define dbg(x) cerr << "[DBG] " << #x << " = " << (x) << '\n'
template <class A, class B>
ostream &operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ',' << p.second << ')'; }
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << '[';
    for (size_t i = 0; i < v.size(); ++i)
    {
        if (i)
            os << ',';
        os << v[i];
    }
    return os << ']';
}
template <class K, class V>
ostream &operator<<(ostream &os, const map<K, V> &mp)
{
    os << '{';
    bool first = true;
    for (const auto &kv : mp)
    {
        if (!first)
            os << ',';
        first = false;
        os << kv.first << ':' << kv.second;
    }
    return os << '}';
}
template <class K, class V>
ostream &operator<<(ostream &os, const unordered_map<K, V> &mp)
{
    os << '{';
    bool first = true;
    for (const auto &kv : mp)
    {
        if (!first)
            os << ',';
        first = false;
        os << kv.first << ':' << kv.second;
    }
    return os << '}';
}
#else
#define dbg(x) ((void)0)
#endif

void zanj0()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
}

/*
────────────────────────────────────────────────────────────────────────
    Problem Statement:

    Observations:
    A[i] + A[i + 1] .. A[j] >= C[j]

    pre[j] - pre[i - 1] >= C[j]
    pre[j] - C[j] >= pre[i - 1]


    dp[j] -> max moves to reach there.
    dp[j] = max move of dp[i] where pre[i]<= pre[j] - C[j]

    Claims:

────────────────────────────────────────────────────────────────────────
*/
const lli OFF_SET = 5;
class Fenwick
{
public:
    lli *arr;
    lli n;
    Fenwick(lli n)
    {
        n += OFF_SET;
        arr = new lli[n]();
        for (int i = 0; i < n; i++)
            arr[i] = -1;
        this->n = n;
    }
    void add(lli idx, lli val)
    {
        idx += OFF_SET;
        while (idx < n)
        {
            arr[idx] = max(arr[idx], val);
            idx += idx & -idx;
        }
    }
    lli query(lli idx)
    {
        idx += OFF_SET;
        lli ret = -1;
        while (idx > 0)
        {
            ret = max(ret, arr[idx]);
            idx -= idx & (-idx);
        }
        return ret;
    }
    lli rangeQuery(lli l, lli r)
    {
        return query(r) - (l == 0 ? 0 : query(l - 1));
    }
};
template <typename T>
struct Compressor
{
    vector<T> vals;
    void add(const T &x) { vals.pb(x); }
    void build()
    {
        sort(vals.begin(), vals.end());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());
    }
    int get(const T &x) { return (int)(lower_bound(vals.begin(), vals.end(), x) - vals.begin()); }
    int idx_of(const T &x)
    {
        auto it = lower_bound(vals.begin(), vals.end(), x);
        return (it != vals.end() && *it == x) ? int(it - vals.begin()) : -1;
    }
    int size() const { return (int)vals.size(); }
};

void Solve()
{
    lli n;
    cin >> n;

    vector<lli> 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];
    }

    vector<lli> pre(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        pre[i] = pre[i - 1] + a[i];
    }

    Compressor<lli> compressor = Compressor<lli>();
    for (auto &it : pre)
    {
        compressor.add(it);
    }

    compressor.build();

    Fenwick f(compressor.size() + 5);
    f.add(compressor.get(0), 0);
    if (n == 1)
    {
        cout << 0 << endl;
        return;
    }
    for (int i = 2; i <= n; i++)
    {
        lli curr = pre[i] - c[i];
        int q = upper_bound(compressor.vals.begin(), compressor.vals.end(), curr) - compressor.vals.begin() - 1;
        if (q < 0)
            continue;
        lli best = f.query(q);
        if (best == -1)
            continue;
        f.add(compressor.get(pre[i - 1]), best + 1);
        if (i == n)
        {
            cout << best+1 << endl;
            return;
        }
    }
    cout << -1 << endl;
}

int32_t main()
{
    zanj0();
    w(t) Solve();
    timetaken;
    return 0;
}

/*
    GOLDEN RULES
    • Solutions are simple.
    • Proofs are simple.
    • Implementations are simple.
*/

Information

Submit By
Type
Submission
Problem
P1199 F. Roy and Path Game
Contest
Happy New Year 2026
Language
C++17 (G++ 13.2.0)
Submit At
2026-01-06 15:45:39
Judged At
2026-01-06 15:45:39
Judged By
Score
100
Total Time
231ms
Peak Memory
19.723 MiB