#283750 (C90) No.649 ここでちょっとQK！

• 問題: No.649 ここでちょっとQK！
• ユーザー: akakimidori
• 提出日時: 2018-09-08 14:04:18
• 言語: C90 (gcc 11.4.0)
• 結果: AC
• 実行時間: 81 ms / 3,000 ms
• コード長: 1,870 bytes
• コンパイル時間: 1,147 ms
• コンパイル使用メモリ: 22,400 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-05-09 13:13:45
• 合計ジャッジ時間: 4,851 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	0 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	23 ms; 5,376 KB
testcase_04	AC	81 ms; 5,376 KB
testcase_05	AC	57 ms; 5,376 KB
testcase_06	AC	59 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	AC	1 ms; 5,376 KB
testcase_09	AC	0 ms; 5,376 KB
testcase_10	AC	1 ms; 5,376 KB
testcase_11	AC	1 ms; 5,376 KB
testcase_12	AC	32 ms; 5,376 KB
testcase_13	AC	32 ms; 5,376 KB
testcase_14	AC	31 ms; 5,376 KB
testcase_15	AC	34 ms; 5,376 KB
testcase_16	AC	31 ms; 5,376 KB
testcase_17	AC	40 ms; 5,376 KB
testcase_18	AC	45 ms; 5,376 KB
testcase_19	AC	49 ms; 5,376 KB
testcase_20	AC	53 ms; 5,376 KB
testcase_21	AC	56 ms; 5,376 KB
testcase_22	AC	61 ms; 5,376 KB
testcase_23	AC	66 ms; 5,376 KB
testcase_24	AC	69 ms; 5,376 KB
testcase_25	AC	73 ms; 5,376 KB
testcase_26	AC	77 ms; 5,376 KB
testcase_27	AC	1 ms; 5,376 KB
testcase_28	AC	0 ms; 5,376 KB
testcase_29	AC	1 ms; 5,376 KB
testcase_30	AC	26 ms; 5,376 KB
testcase_31	AC	29 ms; 5,376 KB
testcase_32	AC	1 ms; 5,376 KB
testcase_33	AC	1 ms; 5,376 KB
testcase_34	AC	0 ms; 5,376 KB
testcase_35	AC	0 ms; 5,376 KB

コンパイルメッセージ

main.c: In function ‘run’:
main.c:71:3: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   71 |   scanf("%d%d",&q,&k);
      |   ^~~~~~~~~~~~~~~~~~~
main.c:76:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   76 |     scanf("%d",&c);
      |     ^~~~~~~~~~~~~~
main.c:79:7: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   79 |       scanf("%lld",&v);
      |       ^~~~~~~~~~~~~~~~

ソースコード

#include<stdio.h>
#include<stdlib.h>

typedef long long int int64;

typedef int64 node;

typedef struct binaryHeap{
  node *h;
  int size;
  int (*cmp)(const node*,const node*);
} heap;

heap* init(int maxSize,int (*cmpF)(const node*,const node*)){
  heap *res=(heap *)malloc(sizeof(heap));
  res->h=(node *)malloc(sizeof(node)*(maxSize+1));
  res->size=0;
  res->cmp=cmpF;
  return res;
}

void push(heap *q,const node *p){
  q->size+=1;
  int k=q->size;
  int (*cmp)(const node*,const node*)=q->cmp;
  q->h[k]=*p;
  while(k>1){
    if(cmp(q->h+k/2,q->h+k)) return;
    node swap=q->h[k/2];
    q->h[k/2]=q->h[k];
    q->h[k]=swap;
    k/=2;
  }
  return;
}

void pop(heap *q,node *res){
  node *h=q->h;
  *res=h[1];
  h[1]=h[q->size];
  q->size-=1;
  int n=q->size;
  int (*cmp)(const node*,const node*)=q->cmp;
  int k=1;
  while(2*k+1<=n){
    int next=cmp(h+2*k,h+2*k+1)?2*k:2*k+1;
    if(cmp(h+k,h+next)) return;
    node swap=h[k];
    h[k]=h[next];
    h[next]=swap;
    k=next;
  }
  if(2*k<=n && cmp(h+2*k,h+k)){
    node swap=h[k];
    h[k]=h[2*k];
    h[2*k]=swap;
  }
  return;
}

int cmpMin(const node *a,const node *b){
  return *a<=*b;
}

int cmpMax(const node *a,const node *b){
  return !cmpMin(a,b);
}

void run(void){
  int q,k;
  scanf("%d%d",&q,&k);
  heap *maxHeap=init(k,cmpMax);
  heap *minHeap=init(q,cmpMin);
  while(q--){
    int c;
    scanf("%d",&c);
    if(c==1){
      int64 v;
      scanf("%lld",&v);
      if(maxHeap->size<k){
	push(maxHeap,&v);
      } else if(maxHeap->h[1]>v){
	int64 u;
	pop(maxHeap,&u);
	push(maxHeap,&v);
	push(minHeap,&u);
      } else {
	push(minHeap,&v);
      }
    } else {
      if(maxHeap->size==k){
	int64 v;
	pop(maxHeap,&v);
	printf("%lld\n",v);
	if(minHeap->size>0){
	  pop(minHeap,&v);
	  push(maxHeap,&v);
	}
      } else {
	printf("-1\n");
      }
    }
  }
}

int main(void){
  run();
  return 0;
}