/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 2ms 576.0 KiB
#3 Accepted 2ms 364.0 KiB
#4 Accepted 3ms 576.0 KiB
#5 Accepted 72ms 580.0 KiB
#6 Accepted 105ms 588.0 KiB
#7 Accepted 84ms 992.0 KiB
#8 Accepted 496ms 54.41 MiB
#9 Accepted 407ms 11.605 MiB
#10 Accepted 46ms 632.0 KiB
#11 Accepted 25ms 532.0 KiB
#12 Accepted 603ms 53.559 MiB
#13 Accepted 108ms 604.0 KiB
#14 Accepted 450ms 54.199 MiB
#15 Accepted 472ms 54.379 MiB

Code

#include<bits/stdc++.h>

#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>


#ifdef _MSC_VER
#include <intrin.h>
#endif

#if __cplusplus >= 202002L
#include <bit>
#endif

namespace atcoder {

namespace internal {

#if __cplusplus >= 202002L

using std::bit_ceil;

#else

unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n)) x *= 2;
    return x;
}

#endif

int countr_zero(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

constexpr int countr_zero_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

}  // namespace internal

}  // namespace atcoder


namespace atcoder {

#if __cplusplus >= 201703L

template <class S, auto op, auto e> struct segtree {
    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
                  "op must work as S(S, S)");
    static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
                  "e must work as S()");

#else

template <class S, S (*op)(S, S), S (*e)()> struct segtree {

#endif

  public:
    segtree() : segtree(0) {}
    explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
    explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {
        size = (int)internal::bit_ceil((unsigned int)(_n));
        log = internal::countr_zero((unsigned int)size);
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) const {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() const { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) const {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) const {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) const {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) const {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

}  // namespace atcoder

using namespace std;
using namespace atcoder;

using ll=long long;
using pl=pair<ll,ll>;

ll op(ll a,ll b){return max(a,b);}
ll e(){return -1e18;}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  mt19937_64 engine(0);
  int t;
  cin >> t;
  while(t>0){
    t--;
    ll n;
    n=1+engine()%10;
    cin >> n;
    vector<ll> a(n+1);
    vector<ll> c(n+1);
    // for(ll i=1;i<=n;i++){a[i]=-9+engine()%19;}
    // for(ll i=1;i<=n;i++){c[i]=-9+engine()%19;}
    // cerr << n << "\n";
    // for(auto &nx : a){cerr << nx << " ";}cerr << "\n";
    // for(auto &nx : c){cerr << nx << " ";}cerr << "\n";
    for(ll i=1;i<=n;i++){cin >> a[i];}
    for(ll i=1;i<=n;i++){cin >> c[i];}

    // vector<ll> dp(n+1,-1e9);
    // dp[1]=0;
    // for(ll i=1;i<=n;i++){
    //   ll sa=a[i];
    //   for(ll j=i+1;j<=n;j++){
    //     sa+=a[j];
    //     if(sa>=c[j]){
    //       dp[j]=max(dp[j],dp[i]+1);
    //     }
    //   }
    // }

    // if(dp[n]<-5e8){dp[n]=-1;}
    if(n==1){
      // assert(dp[n]==0);
      cout << "0\n";
      continue;
    }
    // cerr << dp[n] << "\n";

    vector<ll> h(n+1,0);
    h[0]=0;
    for(ll i=1;i<=n;i++){ h[i]=h[i-1]+a[i]; }
    map<ll,ll> mp;
    for(auto &nx : h){mp[nx]=0;}
    ll hh=0;
    for(auto &nx : mp){nx.second=hh; hh++;}

    segtree<ll,op,e> seg(n+5);
    seg.set(mp[0],0);
    for(ll i=2;i<=n;i++){
      auto it=mp.upper_bound(h[i]-c[i]);
      ll tg;
      if(it==mp.end()){tg=n+5;}
      else{tg=(*it).second;}
      ll ct=seg.prod(0,tg)+1;
      if(i==n){
        if(ct<0){ct=-1;}
        // assert(dp[n]==ct);
        cout << ct << "\n";
        break;
      }
      ll pp=mp[h[i-1]];
      seg.set(pp,max(seg.get(pp),ct));
    }
  }
  return 0;
}

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 16:07:09
Judged At
2026-01-06 16:07:09
Judged By
Score
100
Total Time
603ms
Peak Memory
54.41 MiB