Submission #76175796

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <stdlib.h>
int qsize = 0;
int q[312345];
void qadjust(int pos) {
  for (;;) {
    int minpos = pos;
    int i;
    for (i = 1; i <= 2; i++) {
      int c = pos * 2 + i;
      if (c < qsize && q[minpos] > q[c]) minpos = c;
    }
    if (minpos == pos) {
      if (pos == 0) return;
      pos = (pos - 1) / 2;
    } else {
      int t = q[minpos];
      q[minpos] = q[pos];
      q[pos] = t;
      pos = minpos;
    }
  }
}
void qadd(int value) {
  q[qsize++] = value;
  qadjust(qsize - 1);
}
int qget(void) {
  int v;
  if (qsize <= 0) exit(72);
  v = q[0];
  if (--qsize > 0) {
    q[0] = q[qsize];
    qadjust(0);
  }
  return v;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

int qsize = 0;
int q[312345];

void qadjust(int pos) {
	for (;;) {
		int minpos = pos;
		int i;
		for (i = 1; i <= 2; i++) {
			int c = pos * 2 + i;
			if (c < qsize && q[minpos] > q[c]) minpos = c;
		}
		if (minpos == pos) {
			if (pos == 0) return;
			pos = (pos - 1) / 2;
		} else {
			int t = q[minpos];
			q[minpos] = q[pos];
			q[pos] = t;
			pos = minpos;
		}
	}
}

void qadd(int value) {
	q[qsize++] = value;
	qadjust(qsize - 1);
}

int qget(void) {
	int v;
	if (qsize <= 0) exit(72);
	v = q[0];
	if (--qsize > 0) {
		q[0] = q[qsize];
		qadjust(0);
	}
	return v;
}

int main(void) {
	int Q, i;
	if (scanf("%d", &Q) != 1) return 1;
	for (i = 0; i < Q; i++) {
		int type, h;
		if (scanf("%d%d", &type, &h) != 2) return 1;
		if (type == 1) {
			qadd(h);
		} else if (type == 2) {
			while (qsize > 0 && q[0] <= h) qget();
		}
		printf("%d\n", qsize);
	}
	return 0;
}

Submission Info

Judge Result