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

airport Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

airport.html

Problem Description

An airport is a location where aircraft such as fixed-wing aircraft, helicopters, and blimps take off and land. Aircraft may be stored or maintained at an airport.

~ Wikipedia

Squeaky International Airport (SIA) is one of the busiest airports in the world. As such, its berths are usually filled, and due to limited supply, the airport tax for landing at the airport is pretty high. Like any other profit-driven corporation, the aim of SIA is to maximise the taxes that it can collect from the aircraft.

The tax is very simple to calculate - it is simply $1000 per aircraft, no matter how big or how long it berths at the airport.

It is reaching the Christmas season, and submissions of application for landing at the airport has quadrupled.

As SIA's hired flight schedule manager, you are tasked to approve or reject each application, in order for SIA to collect the most taxes, but yet have enough berths for all the aircrafts at all times.

You may assume that landing and taking off do not take any time.

The same berth can be used for a flight which takes off at the same time as a flight that lands.

Input

The first line contains two integers, N (1 ≤ N ≤ 1000000), the number of applications, and B (1 ≤ B ≤ 1000000), the number of berths in the airport.

The next N lines contain the applications (in no particular order). Each of these lines contain two integers, Li and Ti (0 ≤ Li < Ti ≤ 232 − 1), the time that the aircraft lands and takes off respectively.

Output

Output N lines, each line containing a string either "APPROVED" or "REJECTED" stating if the application has been approved or rejected, in the same order as given in the input.

There might be more than one solution and all such solutions will be accepted.

Constraints

Subtask 1 (0 points): Sample

Subtask 2 (10 points): 1 ≤ N ≤ 20; B = 1

Subtask 3 (30 points): B = 1

Subtask 4 (60 points): No constraints

Sample Input

3 1
1 10
5 14
12 20 

Sample Output

APPROVED
REJECTED
APPROVED

Tags

Greedy, Sorting

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
110205s128MBMinimum
230305s128MBMinimum
3601105s128MBMinimum
4015s128MBMinimum

Judge Compile Command

g++-8 ans.cpp -o airport -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.