You are given q events from one day at a bakery, in the order they happened.
There are two kinds of event.
"bake t e c" means that at time t a batch of c loaves was baked, and these loaves may be sold up to and including time e.
"buy t k" means that at time t one customer came to buy k loaves.
When a customer comes, the bakery sells only loaves that can be sold at that time, that is, loaves with e ≥ t.
Among those, it hands out k loaves, earliest expiry e first.
Part of a batch may be sold; the rest of the batch stays with the same expiry.
If fewer than k loaves can be sold, the customer gets all of them.
Among loaves with the same expiry, the order does not change the answer.
Events at the same time happen in the order they appear in the input.
For each buy event, print on one line the number of loaves the customer got and the sum of (e − t) over those loaves (the total remaining shelf life), separated by a space.
If the customer got nothing, print "0 0".
Input
The first line has q, and each of the next q lines has one event. 1 ≤ q ≤ 10,000, 0 ≤ t ≤ e ≤ 1,000,000,000, 1 ≤ c, k ≤ 1,000,000. The times t never decrease, and there is at least one buy event.
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Put the batches in a min-heap keyed by the expiry e, and you can always sell from the top (the earliest expiry). Expired batches need not be found ahead of time: when a customer comes, pop and discard the top while e < t (lazy deletion) — times never decrease, so a batch that has expired can never be sold again. A batch is one entry [expiry, count left], not one entry per loaf (c can be a million). When part of a batch is sold, just lower the count; the expiry (the key) is unchanged, so the heap order stays valid. Trap one: a loaf can still be sold on its expiry time (e == t) — discarding on e <= t is wrong. Trap two: with a max-heap the latest expiry goes first. The first customer in the example gets "4 4" with a min-heap but "4 6" with a max-heap. C++ std::priority_queue is a max-heap by default, so it needs std::greater<std::pair<long long, long long>>, and since top() cannot be modified, pop it and push back what is left. Trap three: popping a partly sold batch as a whole throws away its remaining loaves. Trap four: the life sum can reach a million × a billion = 10^15, past a 32-bit int (about 2.1 billion). C and C++ need long long, Java and C# long; Python integers have no limit, and JavaScript, TypeScript and Craykon numbers are doubles, exact up to 2^53 (about 9×10^15), so they work as they are. Heaps differ by language: Python heapq compares the list [expiry, count] from the first item, so it just works, and heap[0][1] may be changed; Java PriorityQueue<long[]> takes the compare function (x, y) -> Long.compare(x[0], y[0]), and the array seen with peek() can be changed; C# PriorityQueue<long[], long> takes the value and the priority (the expiry) separately, and TryPeek shows both. JavaScript, TypeScript, C and Craykon have no heap, so build one on a list (array): the parent of i is (i - 1) / 2 (integer division — Craykon Mathf.Quot(i - 1, 2)), the children 2i + 1 and 2i + 2. Craykon splits a line with Console.ReadLine().Trim().Split(" ") and turns words into numbers with .ToNumber(). The heap never holds more entries than there are bake events (under 10,000), within the list limit.
Pythonmain.py · 31 lines
import heapqimport syslines = sys.stdin.read().split("\n")q = int(lines[0])heap = [] # [기한, 남은 개수]: 기한이 가장 이른 묶음이 heap[0]out = []for line in lines[1 : 1 + q]: w = line.split() t = int(w[1]) if w[0] == "bake": heapq.heappush(heap, [int(w[2]), int(w[3])]) continue need = int(w[2]) got = 0 total = 0 # 받은 빵마다 (기한 - t)를 더한 값 while need > 0 and heap: e, c = heap[0] if e < t: # 기한이 지난 묶음은 버린다(e == t이면 아직 팔 수 있다) heapq.heappop(heap) continue take = min(c, need) got += take total += take * (e - t) need -= take if take == c: heapq.heappop(heap) else: heap[0][1] = c - take # 개수만 줄인다: 기한은 그대로라 힙 차례가 깨지지 않는다 out.append(f"{got} {total}")print("\n".join(out))
JavaScriptmain.js · 75 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const q = Number(lines[0]);// 최소 힙: 칸마다 [기한, 남은 개수]. heap[0]이 기한이 가장 이른 묶음이고, i의 자식은 2i+1, 2i+2class MinHeap { constructor() { this.items = []; } get size() { return this.items.length; } top() { return this.items[0]; } push(x) { const a = this.items; a.push(x); let i = a.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (a[parent][0] <= a[i][0]) break; [a[parent], a[i]] = [a[i], a[parent]]; i = parent; } } pop() { const a = this.items; const top = a[0]; const last = a.pop(); if (a.length > 0) { a[0] = last; let i = 0; for (;;) { const l = 2 * i + 1, r = l + 1; let small = i; if (l < a.length && a[l][0] < a[small][0]) small = l; if (r < a.length && a[r][0] < a[small][0]) small = r; if (small === i) break; [a[small], a[i]] = [a[i], a[small]]; i = small; } } return top; }}const heap = new MinHeap();const out = [];for (let i = 1; i <= q; i++) { const w = lines[i].trim().split(" "); const t = Number(w[1]); if (w[0] === "bake") { heap.push([Number(w[2]), Number(w[3])]); continue; } let need = Number(w[2]); let got = 0; let total = 0; // 받은 빵마다 (기한 - t)를 더한 값: 10^15까지라 배정밀도 수로도 정확하다 while (need > 0 && heap.size > 0) { const batch = heap.top(); const [e, c] = batch; if (e < t) { // 기한이 지난 묶음은 버린다(e === t이면 아직 팔 수 있다) heap.pop(); continue; } const take = Math.min(c, need); got += take; total += take * (e - t); need -= take; if (take === c) heap.pop(); else batch[1] = c - take; // 개수만 줄인다: 기한은 그대로라 힙 차례가 깨지지 않는다 } out.push(`${got} ${total}`);}console.log(out.join("\n"));
TypeScriptmain.ts · 81 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const q: number = Number(lines[0]);type Batch = [expiry: number, count: number];// 최소 힙: heap[0]이 기한이 가장 이른 묶음이고, i의 자식은 2i+1, 2i+2class MinHeap { private items: Batch[] = []; get size(): number { return this.items.length; } top(): Batch { return this.items[0]; } push(x: Batch): void { const a = this.items; a.push(x); let i = a.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (a[parent][0] <= a[i][0]) break; [a[parent], a[i]] = [a[i], a[parent]]; i = parent; } } pop(): Batch { const a = this.items; const top = a[0]; const last = a.pop()!; // size > 0일 때만 부른다 if (a.length > 0) { a[0] = last; let i = 0; for (;;) { const l = 2 * i + 1, r = l + 1; let small = i; if (l < a.length && a[l][0] < a[small][0]) small = l; if (r < a.length && a[r][0] < a[small][0]) small = r; if (small === i) break; [a[small], a[i]] = [a[i], a[small]]; i = small; } } return top; }}const heap = new MinHeap();const out: string[] = [];for (let i = 1; i <= q; i++) { const w: string[] = lines[i].trim().split(" "); const t: number = Number(w[1]); if (w[0] === "bake") { heap.push([Number(w[2]), Number(w[3])]); continue; } let need: number = Number(w[2]); let got = 0; let total = 0; // 받은 빵마다 (기한 - t)를 더한 값: 10^15까지라 number로도 정확하다 while (need > 0 && heap.size > 0) { const batch: Batch = heap.top(); const [e, c] = batch; if (e < t) { // 기한이 지난 묶음은 버린다(e === t이면 아직 팔 수 있다) heap.pop(); continue; } const take: number = Math.min(c, need); got += take; total += take * (e - t); need -= take; if (take === c) heap.pop(); else batch[1] = c - take; // 개수만 줄인다: 기한은 그대로라 힙 차례가 깨지지 않는다 } out.push(`${got} ${total}`);}console.log(out.join("\n"));
JavaMain.java · 44 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.PriorityQueue;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int q = Integer.parseInt(in.readLine().trim()); // {기한, 남은 개수}를 기한이 이른 것부터 꺼내는 최소 힙 PriorityQueue<long[]> heap = new PriorityQueue<>((x, y) -> Long.compare(x[0], y[0])); StringBuilder out = new StringBuilder(); for (int i = 0; i < q; i++) { StringTokenizer st = new StringTokenizer(in.readLine()); String kind = st.nextToken(); long t = Long.parseLong(st.nextToken()); if (kind.equals("bake")) { long e = Long.parseLong(st.nextToken()); long c = Long.parseLong(st.nextToken()); heap.add(new long[] {e, c}); continue; } long need = Long.parseLong(st.nextToken()); long got = 0; long total = 0; // 받은 빵마다 (기한 - t)를 더한 값: 10^15까지라 long이 필요하다 while (need > 0 && !heap.isEmpty()) { long[] batch = heap.peek(); if (batch[0] < t) { // 기한이 지난 묶음은 버린다(같은 시각이면 아직 팔 수 있다) heap.poll(); continue; } long take = Math.min(batch[1], need); got += take; total += take * (batch[0] - t); need -= take; if (take == batch[1]) heap.poll(); else batch[1] -= take; // 개수만 줄인다: 기한은 그대로라 힙 차례가 깨지지 않는다 } out.append(got).append(' ').append(total).append('\n'); } System.out.print(out); }}
C#Main.cs · 44 lines
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { int q = int.Parse(Console.ReadLine().Trim()); // PriorityQueue<값, 우선순위>: 우선순위(기한)가 이른 묶음부터 나온다. // 값은 남은 개수를 고칠 수 있게 길이 1짜리 배열로 둔다 var heap = new PriorityQueue<long[], long>(); var sb = new StringBuilder(); for (int i = 0; i < q; i++) { string[] w = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); long t = long.Parse(w[1]); if (w[0] == "bake") { heap.Enqueue(new long[] { long.Parse(w[3]) }, long.Parse(w[2])); continue; } long need = long.Parse(w[2]); long got = 0; long total = 0; // 받은 빵마다 (기한 - t)를 더한 값: 10^15까지라 long이 필요하다 while (need > 0 && heap.TryPeek(out long[] left, out long e)) { if (e < t) // 기한이 지난 묶음은 버린다(같은 시각이면 아직 팔 수 있다) { heap.Dequeue(); continue; } long take = Math.Min(left[0], need); got += take; total += take * (e - t); need -= take; if (take == left[0]) heap.Dequeue(); else left[0] -= take; // 개수만 줄인다: 우선순위(기한)는 그대로다 } sb.Append(got).Append(' ').Append(total).Append('\n'); } Console.Write(sb.ToString()); }}
C++main.cpp · 45 lines
#include <algorithm>#include <iostream>#include <queue>#include <string>#include <utility>#include <vector>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int q; std::cin >> q; // (기한, 남은 개수): std::greater를 줘야 기한이 이른 것부터 나온다(기본은 최대 힙) using Batch = std::pair<long long, long long>; std::priority_queue<Batch, std::vector<Batch>, std::greater<Batch>> heap; std::string out; for (int i = 0; i < q; i++) { std::string kind; long long t; std::cin >> kind >> t; if (kind == "bake") { long long e, c; std::cin >> e >> c; heap.push({e, c}); continue; } long long need; std::cin >> need; long long got = 0, total = 0; // total: 받은 빵마다 (기한 - t)를 더한 값, 10^15까지 while (need > 0 && !heap.empty()) { auto [e, c] = heap.top(); heap.pop(); if (e < t) continue; // 기한이 지난 묶음은 버린다(같은 시각이면 아직 팔 수 있다) long long take = std::min(c, need); got += take; total += take * (e - t); need -= take; // top()은 고칠 수 없으니 꺼낸 뒤 남은 것을 다시 넣는다(기한이 같아 다시 맨 앞에 온다) if (take < c) heap.push({e, c - take}); } out += std::to_string(got) + " " + std::to_string(total) + "\n"; } std::cout << out; return 0;}
Cmain.c · 74 lines
#include <stdio.h>#include <string.h>#define MAXQ 10000/* 최소 힙: 칸마다 (기한, 남은 개수). heap_e[0]이 기한이 가장 이르다 */static long long heap_e[MAXQ], heap_c[MAXQ];static int heap_size = 0;static void heap_swap(int i, int j) { long long t = heap_e[i]; heap_e[i] = heap_e[j]; heap_e[j] = t; t = heap_c[i]; heap_c[i] = heap_c[j]; heap_c[j] = t;}static void heap_push(long long e, long long c) { int i = heap_size++; heap_e[i] = e; heap_c[i] = c; while (i > 0 && heap_e[(i - 1) / 2] > heap_e[i]) { heap_swap((i - 1) / 2, i); i = (i - 1) / 2; }}static void heap_pop(void) { heap_size--; heap_e[0] = heap_e[heap_size]; heap_c[0] = heap_c[heap_size]; int i = 0; for (;;) { int l = 2 * i + 1, r = l + 1, small = i; if (l < heap_size && heap_e[l] < heap_e[small]) small = l; if (r < heap_size && heap_e[r] < heap_e[small]) small = r; if (small == i) break; heap_swap(small, i); i = small; }}int main(void) { int q; if (scanf("%d", &q) != 1) return 0; for (int i = 0; i < q; i++) { char kind[8]; long long t; scanf("%7s %lld", kind, &t); if (strcmp(kind, "bake") == 0) { long long e, c; scanf("%lld %lld", &e, &c); heap_push(e, c); continue; } long long need, got = 0, total = 0; /* total: 받은 빵마다 (기한 - t)를 더한 값, 10^15까지 */ scanf("%lld", &need); while (need > 0 && heap_size > 0) { if (heap_e[0] < t) { /* 기한이 지난 묶음은 버린다(같은 시각이면 아직 팔 수 있다) */ heap_pop(); continue; } long long take = heap_c[0] < need ? heap_c[0] : need; got += take; total += take * (heap_e[0] - t); need -= take; if (take == heap_c[0]) heap_pop(); else heap_c[0] -= take; /* 개수만 줄인다: 기한은 그대로라 힙 차례가 깨지지 않는다 */ } printf("%lld %lld\n", got, total); } return 0;}
Craykonmain.cray · 91 lines
// 최소 힙(목록 heap): 칸마다 [기한, 남은 개수]. heap[0]이 기한이 가장 이른 묶음이고, i의 자식은 2i+1, 2i+2힙넣기(heap, x){ heap.Add(x); i = heap.Count - 1; while (i > 0) { 부모 = Mathf.Quot(i - 1, 2); if (heap[부모][0] <= heap[i][0]) { break; } t = heap[부모]; heap[부모] = heap[i]; heap[i] = t; i = 부모; }}힙빼기(heap){ heap[0] = heap[heap.Count - 1]; heap.RemoveAt(heap.Count - 1); i = 0; while (true) { l = 2 * i + 1; r = l + 1; small = i; if (l < heap.Count && heap[l][0] < heap[small][0]) { small = l; } if (r < heap.Count && heap[r][0] < heap[small][0]) { small = r; } if (small == i) { break; } t = heap[small]; heap[small] = heap[i]; heap[i] = t; i = small; }}q = Console.ReadLine().Trim().ToNumber();heap = [];for (n = 0; n < q; n++){ w = Console.ReadLine().Trim().Split(" "); t = w[1].ToNumber(); if (w[0] == "bake") { 힙넣기(heap, [w[2].ToNumber(), w[3].ToNumber()]); } else { need = w[2].ToNumber(); got = 0; total = 0; // 받은 빵마다 (기한 - t)를 더한 값 while (need > 0 && heap.Count > 0) { batch = heap[0]; e = batch[0]; c = batch[1]; if (e < t) { 힙빼기(heap); } else { take = Mathf.Min(c, need); got += take; total += take * (e - t); need -= take; if (take == c) { 힙빼기(heap); } else { batch[1] = c - take; // 개수만 줄인다: 기한은 그대로라 힙 차례가 깨지지 않는다 } } } Console.WriteLine(got + " " + total); }}