結果

問題 No.649 ここでちょっとQK!
ユーザー Kenta NakajimaKenta 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0