oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

speakers Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

speakers.html

Problem Description

Peanut is organising a talk today with a group of N people. The stage is M meters wide and the N people are seated in a line, each of them Di meters from the leftmost edge of the stage. Peanut wants to place some speakers along the line so that everyone can hear his speech. However, some people have hearing loss. Thus, each person i requires them to be at most Ri away from a speaker. Help Peanut determine what is the minimum number of speakers he needs to place such that everyone can hear his speech.

Limits

Subtask 1 (14%): 1 ≤ N, M ≤ 15.
Subtask 2 (16%): 1 ≤ N, M ≤ 1 000.
Subtask 3 (21%): 1 ≤ N, M ≤ 100 000.
Subtask 4 (49%): 1 ≤ N ≤ 100 000. 1 ≤ M ≤ 1 000 000 000.
Subtask 5 (0%): Sample testcase.

Input

The first line of input contains two integers, N and M.
The next N lines of input contains two integers each, Di and Ri.

Output

The output should contain one integer, the minimum number of speakers required such that everyone can hear his speech.

Sample Input 1

3 3
0 1
1 1
2 1

Sample Output 1

1

Sample Input 2

4 6
0 2
3 1
4 1
5 2

Sample Output 2

2

Tags

Greedy

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
114201s256MBMinimum
216201s256MBMinimum
321201s256MBMinimum
449201s256MBMinimum
5021s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o speakers -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.