Queueing with Stools (APCS 2019-02 Expert)

2.0s 256M

There are \(n\) people in a queue; people \(1\) through \(i-1\) stand ahead of person \(i\). Person \(i\) has height \(h_i\) and observes the queue while standing on a stool of height \(p_i\). The nearest earlier person whose original height is strictly greater than \(h_i+p_i\) blocks the view. Person \(i\) sees everyone between them, excluding the blocker; if no blocker exists, all earlier people are visible. Earlier people are always compared using their original heights. Find the sum of visible-person counts.

Input Format

The first line contains \(n\). The second lists heights \(h_i\), and the third lists stool heights \(p_i\).

Output Format

Print the total number of visible people summed over all observers.

Constraints

\(1\le n\le200000\), \(1\le h_i\le10^7\), \(0\le p_i\le10^7\).

Sample Input

5
5 4 1 1 3
0 0 4 0 1

Sample Output

6

Source

APCS 2019-02 public archive version: tcirc:d029。

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.