/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 284.0 KiB
#2 Accepted 1ms 284.0 KiB
#3 Accepted 1ms 284.0 KiB
#4 Accepted 2ms 284.0 KiB
#5 Accepted 38ms 1.918 MiB
#6 Accepted 29ms 3.391 MiB
#7 Accepted 23ms 2.133 MiB
#8 Accepted 121ms 27.844 MiB
#9 Accepted 129ms 8.824 MiB
#10 Accepted 10ms 1.246 MiB
#11 Accepted 11ms 1.07 MiB
#12 Accepted 184ms 27.258 MiB
#13 Accepted 45ms 3.609 MiB
#14 Accepted 116ms 25.707 MiB
#15 Accepted 122ms 28.008 MiB

Code

// Author: @Drydock

use std::io::{self, Read};

fn main() {

    solve();

}

fn solve() {

    let mut b = Vec::new();

    io::stdin().read_to_end(&mut b).unwrap();

    let mut it = I { b, i: 0 };

    let t = it.u();

    let mut o = String::new();

    for _ in 0..t {

        let n = it.u();

        let mut a = vec![0i64; n + 1];

        for i in 1..=n {

            a[i] = it.i();

        }

        let mut c = vec![0i64; n + 1];

        for i in 1..=n {

            c[i] = it.i();

        }

        if n == 1 {

            pn(&mut o, 0);

            continue;

        }

        let mut p = vec![0i64; n + 1];

        for i in 1..=n {

            p[i] = p[i - 1] + a[i];

        }

        let mut v = Vec::with_capacity(n);

        for i in 0..n {

            v.push(p[i]);

        }

        v.sort_unstable();

        v.dedup();

        let m = v.len();

        let mut ix = vec![0usize; n];

        for i in 0..n {

            ix[i] = lb(&v, p[i]) + 1;

        }

        let mut f = F::new(m);

        f.u(ix[0], 0);

        let mut an = NI;

        for j in 2..=n {

            let b = p[j] - c[j];

            let k = ub(&v, b);

            let q = f.q(k);

            let dj = if q == NI { NI } else { q + 1 };

            if dj != NI {

                f.u(ix[j - 1], dj);

            }

            if j == n {

                an = dj;

            }

        }

        if an == NI {

            pn(&mut o, -1);

        } else {

            pn(&mut o, an);

        }

    }

    print!("{o}");

}

const NI: i32 = -1000000_000;

fn lb(a: &[i64], x: i64) -> usize {

    let mut l = 0usize;

    let mut r = a.len();

    while l < r {

        let m = (l + r) >> 1;

        if a[m] < x {

            l = m + 1;

        } else {

            r = m;

        }

    }

    l

}

fn ub(a: &[i64], x: i64) -> usize {

    let mut l = 0usize;

    let mut r = a.len();

    while l < r {

        let m = (l + r) >> 1;

        if a[m] <= x {

            l = m + 1;

        } else {

            r = m;

        }

    }

    l

}

fn pn(o: &mut String, x: i32) {

    if x == 0 {

        o.push_str("0\n");

        return;

    }

    if x == -1 {

        o.push_str("-1\n");

        return;

    }

    let mut y = x as i64;

    if y < 0 {

        o.push('-');

        y = -y;

    }

    let mut s = [0u8; 24];

    let mut n = 0usize;

    while y > 0 {

        s[n] = (y % 10) as u8;

        n += 1;

        y /= 10;

    }

    for i in (0..n).rev() {

        o.push((b'0' + s[i]) as char);

    }

    o.push('\n');

}

struct I {

    b: Vec<u8>,

    i: usize,

}

impl I {

    fn u(&mut self) -> usize {

        self.i() as usize

    }

    fn i(&mut self) -> i64 {

        while self.i < self.b.len() && self.b[self.i] <= b' ' {

            self.i += 1;

        }

        let mut s = 1i64;

        if self.b[self.i] == b'-' {

            s = -1;

            self.i += 1;

        }

        let mut x = 0i64;

        while self.i < self.b.len() {

            let c = self.b[self.i];

            if c <= b' ' {

                break;

            }

            x = x * 10 + (c - b'0') as i64;

            self.i += 1;

        }

        s * x

    }

}

struct F {

    n: usize,

    b: Vec<i32>,

}

impl F {

    fn new(n: usize) -> Self {

        Self { n, b: vec![NI; n + 1] }

    }

    fn u(&mut self, mut i: usize, v: i32) {

        while i <= self.n {

            if self.b[i] < v {

                self.b[i] = v;

            }

            i += i & (!i + 1);

        }

    }

    fn q(&self, mut i: usize) -> i32 {

        let mut r = NI;

        while i > 0 {

            let v = self.b[i];

            if r < v {

                r = v;

            }

            i &= i - 1;

        }

        r

    }

}

Information

Submit By
Type
Submission
Problem
P1199 F. Roy and Path Game
Contest
Happy New Year 2026
Language
Rust 2021 (Rust 1.75.0)
Submit At
2026-01-06 16:26:38
Judged At
2026-01-06 16:26:38
Judged By
Score
100
Total Time
184ms
Peak Memory
28.008 MiB