結果

問題 No.649 ここでちょっとQK！
コンテスト
ユーザー akakimidori
提出日時 2018-09-08 14:04:18
言語 C90
(gcc 12.3.0)
結果
AC  
実行時間 74 ms / 3,000 ms
コード長 1,870 bytes
コンパイル時間 905 ms
コンパイル使用メモリ 22,400 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-16 02:38:48
合計ジャッジ時間 4,669 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます
コンパイルメッセージ
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);
      |       ^~~~~~~~~~~~~~~~

ソースコード

diff # 

#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;
}
0