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

similarity Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

similarity.html

Problem Description

Gug is drawing rectangles on a piece of paper, for some reason. Every rectangle that he draws has a certain height H and a certain width W.

Oddly enough, he considers the variation between two different rectangles as min(|Ha - Hb|, |Wa - Wb|), if the first rectangle is of dimensions Ha x Wa and the second rectangle is of dimensions Hb x Wb.

Gug starts off with an empty piece of paper, and he can, at any time, draw a new rectangle or remove an existing rectangle from the piece of paper. It is guaranteed that no two rectangles on the piece of paper at one time will have the exact same dimensions.

To test you, he also can show you a new rectangle, and ask you to find the rectangle on his piece of paper which it is most similar to (least variation). He then wants you to tell him what is its variation to this new rectangle.

Implementation Details

This is a function call question. You are to implement these three functions:

void add_rectangle(int H, int W)

This function should add a rectangle with height H and width W. It is guaranteed that no existing rectangle with the same dimensions already exist on the piece of paper, and that the rectangle dimensions will be between 1 and 109 inclusive.

void erase_rectangle(int H, int W)

This function should remove a rectangle of height H and width W from the piece of paper. It is guaranteed that a rectangle with the exact dimensions exist on the piece of paper.

int test_rectangle(int H, int W)

This function should return the minimum variation between this new rectangle of height H and W and any rectangle currently on his piece of paper. It is guranteed that there is at least one rectangle on his piece of paper, and that the query dimensions are between 1 and 109 inclusive.

Under the Attachments tab, you are provided with a header file, sample grader, solution template, and a compile command. You are advised to test the solution locally before submission to the judge. A sample testcase simulating the sample interaction below is also included.

Limits

Subtask 1 (30%): Total number of calls ≤ 3000.

Subtask 2 (32%): Total number of calls ≤ 300000, erase_rectangle will not be called, all calls to test_rectangle will be done after all calls to add_rectangle.

Subtask 3 (38%): Total number of calls ≤ 300000.

Subtask 4 (0%): Sample Testcases.

Sample Interaction

add_rectangle(3, 5) is called.
add_rectangle(6, 9) is called.
test_rectangle(4, 11) is called. It should return 1.
test_rectangle(1, 3) is called. It should return 2.
erase_rectangle(3, 5) is called.
test_rectangle(4, 11) is called. It should return 2.

Tags

Data Structure

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
130212s256MBMinimum
232202s256MBMinimum
338612s256MBMinimum
4012s256MBMinimum

Attachments

Attachment Filesize Last Updated
sample.out6B5 Dec 2017, 15:00:58
similarity.h105B5 Dec 2017, 15:00:43
grader.cpp326B5 Dec 2017, 15:00:24
ans.cpp217B5 Dec 2017, 15:00:32
compile_command.sh46B5 Dec 2017, 14:48:52
sample.in41B5 Dec 2017, 15:00:52

Judge Compile Command

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