#include #include #include int getN(void) { int n = 0, c; while ((c = getchar()) >= '0' && c <= '9') n = n*10+(c-'0'); return n; } int getI(void) { int n = 0, c = getchar(); if (c == '-') while ((c = getchar()) >= '0' && c <= '9') n = n*10-(c-'0'); else do n = n*10+(c-'0'); while ((c = getchar()) >= '0' && c <= '9'); return n; } void putIs(int n) { char b[12], i = 11; b[11] = ' '; if (n < 0) { n = -n; do b[--i] = (n%10)+'0', n /= 10; while (n); b[--i] = '-'; fwrite(&b[i], sizeof(char), 12-i, stdout); } else { do b[--i] = (n%10)+'0', n /= 10; while (n); fwrite(&b[i], sizeof(char), 12-i, stdout); } } void putIn(int n) { char b[12], i = 11; b[11] = '\n'; if (n < 0) { n = -n; do b[--i] = (n%10)+'0', n /= 10; while (n); b[--i] = '-'; fwrite(&b[i], sizeof(char), 12-i, stdout); } else { do b[--i] = (n%10)+'0', n /= 10; while (n); fwrite(&b[i], sizeof(char), 12-i, stdout); } } typedef struct { int *minHeap; int *minMaxIndexMap; int *maxHeap; int *maxMinIndexMap; int top; } DPQ; DPQ *createDPQ(int size) { DPQ *dpq = malloc(sizeof(DPQ)); if (!dpq) return NULL; dpq->minHeap = malloc(size * sizeof(int)); if (!dpq->minHeap) goto free_dpq; dpq->minMaxIndexMap = malloc((size+1) * sizeof(int)); if (!dpq->minMaxIndexMap) goto free_min_heap; dpq->maxHeap = malloc(size * sizeof(int)); if (!dpq->maxHeap) goto free_min_max_index_map; dpq->maxMinIndexMap = malloc((size+1) * sizeof(int)); if (!dpq->maxMinIndexMap) goto free_max_heap; dpq->minHeap[0] = INT_MIN; dpq->maxHeap[0] = INT_MAX; dpq->top = 0; return dpq; free_max_heap: free(dpq->maxHeap); free_min_max_index_map: free(dpq->minMaxIndexMap); free_min_heap: free(dpq->minHeap); free_dpq: free(dpq); return NULL; } void freeDPQ(DPQ* dpq) { free(dpq->minHeap); free(dpq->minMaxIndexMap); free(dpq->maxHeap); free(dpq->maxMinIndexMap); free(dpq); } void enqueueDPQ(DPQ* dpq, int item) { int i = ++(dpq->top), j = i; while (item < dpq->minHeap[j /= 2]) { dpq->minHeap[i] = dpq->minHeap[j]; dpq->minMaxIndexMap[i] = dpq->minMaxIndexMap[j]; dpq->maxMinIndexMap[dpq->minMaxIndexMap[j]] = i; i = j; } dpq->minHeap[i] = item; int k = i; i = dpq->top, j = i; while (item > dpq->maxHeap[j /= 2]) { dpq->maxHeap[i] = dpq->maxHeap[j]; dpq->maxMinIndexMap[i] = dpq->maxMinIndexMap[j]; dpq->minMaxIndexMap[dpq->maxMinIndexMap[j]] = i; i = j; } dpq->maxHeap[i] = item; dpq->minMaxIndexMap[k] = i, dpq->maxMinIndexMap[i] = k; } void dequeueMinDPQ(DPQ* dpq) { switch (dpq->top) { case 0: return; case 1: --(dpq->top); return; } int trash = dpq->minHeap[1]; int t = dpq->minMaxIndexMap[1]; int item = dpq->minHeap[dpq->top]; int i = 1, j = i, k = dpq->minMaxIndexMap[dpq->top--]; while ((j *= 2) <= dpq->top) { if (j < dpq->top && dpq->minHeap[j+1] < dpq->minHeap[j]) ++j; if (item <= dpq->minHeap[j]) break; dpq->minHeap[i] = dpq->minHeap[j]; dpq->minMaxIndexMap[i] = dpq->minMaxIndexMap[j]; dpq->maxMinIndexMap[dpq->minMaxIndexMap[j]] = i; i = j; } dpq->minHeap[i] = item; dpq->minMaxIndexMap[i] = k, dpq->maxMinIndexMap[k] = i; item = dpq->maxHeap[++(dpq->top)]; i = t, j = i, k = dpq->maxMinIndexMap[dpq->top--]; while (item > dpq->maxHeap[j /= 2]) { dpq->maxHeap[i] = dpq->maxHeap[j]; dpq->maxMinIndexMap[i] = dpq->maxMinIndexMap[j]; dpq->minMaxIndexMap[dpq->maxMinIndexMap[j]] = i; i = j; } dpq->maxHeap[i] = item; dpq->maxMinIndexMap[i] = k, dpq->minMaxIndexMap[k] = i; } void dequeueMaxDPQ(DPQ* dpq) { switch (dpq->top) { case 0: return; case 1: --(dpq->top); return; } int trash = dpq->maxHeap[1]; int t = dpq->maxMinIndexMap[1]; int item = dpq->maxHeap[dpq->top]; int i = 1, j = i, k = dpq->maxMinIndexMap[dpq->top--]; while ((j *= 2) <= dpq->top) { if (j < dpq->top && dpq->maxHeap[j+1] > dpq->maxHeap[j]) ++j; if (item >= dpq->maxHeap[j]) break; dpq->maxHeap[i] = dpq->maxHeap[j]; dpq->maxMinIndexMap[i] = dpq->maxMinIndexMap[j]; dpq->minMaxIndexMap[dpq->maxMinIndexMap[j]] = i; i = j; } dpq->maxHeap[i] = item; dpq->maxMinIndexMap[i] = k, dpq->minMaxIndexMap[k] = i; item = dpq->minHeap[++(dpq->top)]; i = t, j = i, k = dpq->minMaxIndexMap[dpq->top--]; while (item < dpq->minHeap[j /= 2]) { dpq->minHeap[i] = dpq->minHeap[j]; dpq->minMaxIndexMap[i] = dpq->minMaxIndexMap[j]; dpq->maxMinIndexMap[dpq->minMaxIndexMap[j]] = i; i = j; } dpq->minHeap[i] = item; dpq->minMaxIndexMap[i] = k, dpq->maxMinIndexMap[k] = i; } int main(void) { int T = getN(); int k; DPQ *Q = createDPQ(1000001); char b[2]; while (T--) { k = getN(); while (k--) { fread(b, sizeof(char), 2, stdin); if (b[0] == 'I') { enqueueDPQ(Q, getI()); continue; } fread(b, sizeof(char), 2, stdin); if (b[0] == '-') { getchar(); dequeueMinDPQ(Q); continue; } dequeueMaxDPQ(Q); } if (Q->top) { putIs(Q->maxHeap[1]), putIn(Q->minHeap[1]); Q->top = 0; } else fwrite("EMPTY\n", sizeof(char), 6, stdout); } freeDPQ(Q); return 0; }

제출 #17922

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: