結果

問題 No.649 ここでちょっとQK！
ユーザー akakimidoriakakimidori
提出日時 2018-09-08 14:10:32
言語 C90
(gcc 11.4.0)
結果
AC  
実行時間 81 ms / 3,000 ms
コード長 1,780 bytes
コンパイル時間 399 ms
コンパイル使用メモリ 22,400 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-05-09 13:23:37
合計ジャッジ時間 3,627 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 0 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 22 ms
5,376 KB
testcase_04 AC 78 ms
5,376 KB
testcase_05 AC 81 ms
5,376 KB
testcase_06 AC 79 ms
5,376 KB
testcase_07 AC 0 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 0 ms
5,376 KB
testcase_12 AC 36 ms
5,376 KB
testcase_13 AC 32 ms
5,376 KB
testcase_14 AC 32 ms
5,376 KB
testcase_15 AC 44 ms
5,376 KB
testcase_16 AC 32 ms
5,376 KB
testcase_17 AC 40 ms
5,376 KB
testcase_18 AC 43 ms
5,376 KB
testcase_19 AC 49 ms
5,376 KB
testcase_20 AC 55 ms
5,376 KB
testcase_21 AC 58 ms
5,376 KB
testcase_22 AC 62 ms
5,376 KB
testcase_23 AC 66 ms
5,376 KB
testcase_24 AC 73 ms
5,376 KB
testcase_25 AC 76 ms
5,376 KB
testcase_26 AC 81 ms
5,376 KB
testcase_27 AC 1 ms
5,376 KB
testcase_28 AC 1 ms
5,376 KB
testcase_29 AC 1 ms
5,376 KB
testcase_30 AC 32 ms
5,376 KB
testcase_31 AC 28 ms
5,376 KB
testcase_32 AC 0 ms
5,376 KB
testcase_33 AC 1 ms
5,376 KB
testcase_34 AC 0 ms
5,376 KB
testcase_35 AC 1 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);
      |       ^~~~~~~~~~~~~~~~

ソースコード

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+1,cmpMax);
  heap *minHeap=init(q,cmpMin);
  while(q--){
    int c;
    scanf("%d",&c);
    if(c==1){
      int64 v;
      scanf("%lld",&v);
      push(maxHeap,&v);
      if(maxHeap->size>k){
	pop(maxHeap,&v);
	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