結果

問題 No.649 ここでちょっとQK！
コンテスト
ユーザー Kenta Nakajima
提出日時 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);
      |   ^~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#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 heap
static 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 right
        int64_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 left
        int64_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;
}
0