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

potatoqueue Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

potatoqueue.html

Problem Description

Having tried Jiahai the Potato's delicious Shepherd's Pie, Mr. Panda suggested that he set up a stall to sell his pies and make some money. Hence, he sets up stall with help from Mr. Panda in advertising. Within a few months, the stall gets very famous and his stall starts attracting long queues.

Even though Jiahai the Potato is trying his best to serve the pies as quickly as possible, some people in the queue get impatient for having to wait in the long queue so Mr. Panda is made to deal with the impatient customers. The customers joining the queue are of different heights and each customer can only look over customers in front of them that are strictly shorter than them. The customers want to know how far they are from the front and thus bombard Mr. Panda with the question "How many people are there in front of the last person I can see?". He needs your help to answer these queries AS FAST AS POSSIBLE to keep the customers happy.

Implementation Details

Initially, the queue is empty. Your program will have to implement the 4 functions below.

void init(): Initialisation of code

void join(int H): A person of height H joins the back of the queue

void serve(): The front person in the queue is served, there is guaranteed to be someone in the queue

int query(int N): The Nth person from the front makes the query "How many people are there in front of the last person I can see?" and the function should return the answer. If the customer can see the stall and is trolling Mr. Panda, return -1. The query is guaranteed to be valid.

Please use the template provided for coding and for testing purposes you can run compile_cpp.sh to create a program for testing.

Limits

The height of each customer will fit into a 32-bit signed integer.

For all subtasks, the total number of customers and queries will not exceed 106

Subtask 1 (10%): There will be at most 1000 customers and 5000 queries

Subtask 2 (10%): All the customers will be of the same height

Subtask 3 (20%): All calls to query will happen after calls to join and serve

Subtask 4 (20%): No customers will be served :(

Subtask 5 (40%): No restrictions

Sample Input

join 1
join 7
join 4
query 2
query 3
serve
serve
join 2
query 1
query 2

Sample Output

-1
1
-1
0

Tags

Data Structure

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
110105s16MBMinimum
210105s16MBMinimum
320105s16MBMinimum
420105s16MBMinimum
540105s16MBMinimum

Attachments

Attachment Filesize Last Updated
compile_cpp.sh105B11 Dec 2013, 09:38:25
grader.cpp323B11 Dec 2013, 09:38:25
potatoqueue.h62B11 Dec 2013, 09:38:25
potatoqueue.cpp108B11 Dec 2013, 09:38:25

Judge Compile Command

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