結果
問題 | No.649 ここでちょっとQK! |
ユーザー |
|
提出日時 | 2020-06-09 18:58:02 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 67 ms / 3,000 ms |
コード長 | 3,911 bytes |
コンパイル時間 | 1,330 ms |
コンパイル使用メモリ | 27,904 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2025-01-02 13:53:03 |
合計ジャッジ時間 | 3,731 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
コンパイルメッセージ
main.c: In function ‘get_int’: main.c:11:13: warning: format ‘%lld’ expects argument of type ‘long long int *’, but argument 2 has type ‘int64_t *’ {aka ‘long int *’} [-Wformat=] 11 | scanf("%lld", &num); | ~~~^ ~~~~ | | | | | int64_t * {aka long int *} | long long int * | %ld main.c: In function ‘main’: main.c:182:20: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘int64_t’ {aka ‘long int’} [-Wformat=] 182 | printf("%lld\n", ans[i]); | ~~~^ ~~~~~~ | | | | | int64_t {aka long int} | long long int | %ld main.c: In function ‘get_int’: main.c:11:3: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 11 | scanf("%lld", &num); | ^~~~~~~~~~~~~~~~~~~ main.c: In function ‘get_int2’: main.c:16:3: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 16 | scanf("%d %d", a1, a2); | ^~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdint.h> // int64_t#define max(a,b) ((a) > (b) ? (a) : (b))#define min(a,b) ((a) > (b) ? (b) : (a))int64_t get_int(void) {int64_t num;scanf("%lld", &num);return num;}int get_int2(int *a1, int *a2) {scanf("%d %d", a1, a2);return 0;}#define QUERY_MAX 200000#define HEAP_MAX (QUERY_MAX+50)static int64_t max_heap[HEAP_MAX];static int hmax_idx = 1;void swap(int64_t *a1, int64_t *a2) {int64_t tmp = *a1;*a1 = *a2;*a2 = tmp;}int maxcmp(int64_t a1, int64_t a2) {return a1 > a2;}void enqueue_max(int64_t val) {int node = hmax_idx;max_heap[hmax_idx++] = val;int parent;while((parent = node / 2)) {if(maxcmp(max_heap[parent], max_heap[node])) break;swap(&max_heap[parent], &max_heap[node]);node = parent;}return;}int64_t dequeue_max(void) {int64_t ans = max_heap[1];max_heap[1] = max_heap[--hmax_idx];int node = 1;while(1) {int this = node;int left = node * 2;int right = node * 2 + 1;if(left < hmax_idx && !maxcmp(max_heap[this], max_heap[left])) {this = left;}if(right < hmax_idx && !maxcmp(max_heap[this], max_heap[right])) {this = right;}if(this == node) break;swap(&max_heap[this], &max_heap[node]);node = this;}return ans;}// min heapstatic int64_t min_heap[HEAP_MAX];static int hmin_idx = 1;int mincmp(int64_t a1, int64_t a2) {return a1 < a2;}int is_min_heap_empty(void) {return hmin_idx == 1;}void enqueue_min(int64_t val) {int node = hmin_idx;min_heap[hmin_idx++] = val;int parent;while((parent = node / 2)) {if(mincmp(min_heap[parent], min_heap[node])) break;swap(&min_heap[parent], &min_heap[node]);node = parent;}return;}int64_t dequeue_min(void) {int64_t ans = min_heap[1];min_heap[1] = min_heap[--hmin_idx];int node = 1;while(1) {int this = node;int left = node * 2;int right = node * 2 + 1;if(left < hmin_idx && !mincmp(min_heap[this], min_heap[left])) {this = left;}if(right < hmin_idx && !mincmp(min_heap[this], min_heap[right])) {this = right;}if(this == node) break;swap(&min_heap[this], &min_heap[node]);node = this;}return ans;}int size = 0;int get_size(void) {return size;}// max_heap[1] <= min_heap[1]void add(int64_t val, int k) {int64_t mmax = max_heap[1];if(size < k) {enqueue_max(val);size++;return;}if(val >= mmax) {enqueue_min(val);} else {enqueue_max(val);// move rightint64_t nval = dequeue_max();enqueue_min(nval);}size++;}int64_t find_and_delete(int k) {if(size < k) {return -1;}int64_t ans = dequeue_max();if(!is_min_heap_empty()) {// move leftint64_t nval = dequeue_min();enqueue_max(nval);}size--;return ans;}enum query {QUERY_ADD = 1,QUERY_GETK = 2};int main(void) {int num, k;get_int2(&num, &k);int i;int64_t ans[QUERY_MAX];int aidx = 0;for(i = 0; i < num; i++) {int type = get_int();switch(type) {case QUERY_ADD:{int64_t val = get_int();add(val, k);}break;case QUERY_GETK:{ans[aidx++] = find_and_delete(k);}break;default:break;}}for(i = 0; i < aidx; i++) {printf("%lld\n", ans[i]);}return 0;}