TIOJ-1168

2qbingxuan

2020-01-25

進階的入門

https://tioj.ck.tp.edu.tw/problems/1168

Description

你需要實作五個函式：

1
2
3
4
5
void pop_big();
void pop_small();
void push(int s);
int big();
int small();

其中第一個函式需要將最大的數字移除，第二個函式需要將最小的數字移除，第三個函式需要將一個數加入目前的數字們，第四個函式需要回傳當前的最大值，第五個函式需要回傳當前的最小值。
假設一開始沒有任何數字，請你實作這五個操作。

保證當沒有數字的時候只會呼叫 push ，並且加入的數字 $\leq 10^9$ ，五個函數的總呼叫次數 $\leq 10^6$ 。

Solution

好久之前就一直卡這題總算AC了@_@

最直覺的想法就是開一個multiset或map，但這題的時限超誇張的緊
可以想到利用 priority_queue 維護最大最小
然而假如一個數字在最大堆被pop掉，不容易在最小堆裡面把他給刪除

我一開始的想法是開 unordered_map 之類的紀錄每個數字的個數，想當然而吃了TLE
後來查了解才發現紀錄插入編號並且維護編號幾的被 pop 了就可以
於是我就在 priority_queue 裡面存編號，並且自己寫compare函式
不過這樣寫的locality很差，似乎會讓常數暴增

改成用struct包住之後剩下最後兩筆TLE，試了好久之後才想到 priority_queue 是用 vector 實作，動態開的空間顯然會浪費很多常數，不如自己靜態開一個大陣列
注意到 pop 操作最多就是呼叫次數的一半，所以 heap 只要開 5e5 就好了， push 的時候多出去的可以直接丟掉
至於 popped 陣列應該還是要開到 1e6 ，因為被 pop 的東西有可能編號很大，TIOJ上的測資似乎沒考慮到這個地方所以開 5e5 也能AC

AC code

 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
42
43
44
45
46
47
48
49
50
51
#pragma g++ optimize("Ofast")
#pragma loop_opt(on)
#include "lib1168.h"
#define ff first
#define ss second

const int N = 500001;

struct node {
    int val, id;
    bool operator<(const node &b)const{return val<b.val;}
};
struct heap {
    node v[N];
    int sz;
    void push(node x) {
        v[sz++] = x;
        std::push_heap(v,v+sz);
        if(sz >= N) sz = N-1;
    }
    node top() {return v[0];}
    void pop() {
        std::pop_heap(v,v+sz);
        --sz;
    }
} mx, mn;
int tot;
bool popped[N]; // should be N*2?
inline void push(int x) {
    mx.push({x, tot});
    mn.push({-x, tot});
    ++tot;
}
inline int big() {
    while(popped[mx.top().id]) mx.pop();
    return mx.top().val;
}
inline int small() {
    while(popped[mn.top().id]) mn.pop();
    return -mn.top().val;
}
inline void pop_big() {
    while(popped[mx.top().id]) mx.pop();
    popped[mx.top().id] = 1;
    mx.pop();
}
inline void pop_small() {
    while(popped[mn.top().id]) mn.pop();
    popped[mn.top().id] = 1;
    mn.pop();
}