1. 제한시간내에 돌아가는 이유가 궁금합니다.
   문제에는 3초로 되있는데 제 컴퓨터에서는 교재에 있는 정답 코드도 10000을 넘어가면 3초가 넘어갑니다. 100000의 경우는 1분30초 정도 나오는것을 보면 사양의 문제는 아니라고 생각되어 질문을 합니다.

2. priority_queue에서 vector와 deque의 속도차이의 이유를 잘 모르겠습니다.
   priority_queue> first;
   priority_queue> first;
   처음에는 deque로 했었는데 나중에 책과 비교해서 시간을 재보니 deque가 많이 느렸습니다. 예제의 마지막 케이스는 5배 이상 차이가.... deque는 앞뒤로 넣는것이 가능하여 더 효율적으로 동작한다고 생각했는데 시간차이가 이렇게 나는 이유가 궁금합니다.

아래는 제출했던 코드입니다.
~~~ c++

#include
#include
#include
#include
#include

#define MOD 20090711

using namespace std;

struct makeInput{
int a, b, rng;
makeInput(int _a, int _b):a(_a), b(_b), rng(1983){}
int getNext(){
int temp = rng;

rng = (rng*(long long)a+b)%MOD;
return temp;
}
};

class RUNNINGMEDIAN{
public:
void input();
void getMedi();
void Run();
private:
int count;
int n, a, b;
long long rng;
long long result;

};

void RUNNINGMEDIAN::input(){
result = 0;
cin >> n >> a >> b;
}

void RUNNINGMEDIAN::getMedi(){
priority_queue> first;
priority_queue, greater> second;
makeInput m(a, b);

for(int i=0;i<n;i++){
    if(first.size() == second.size())
        first.push(m.getNext());
    else 
        second.push(m.getNext());

    if(!second.empty() && (first.top() > second.top()) ){
        int a = first.top(), b = second.top();
        first.pop(); second.pop();
        first.push(b); second.push(a);
    }

    result = (result + first.top())%MOD;
}

}

void RUNNINGMEDIAN::Run(){
clock_t s, e;
cin >> count;
while(count--){
input();
s = clock();
getMedi();
cout << result << endl;
e = clock();
printf("%f sec\n",(float)(e-s)/CLOCKS_PER_SEC);
}
}

int main(){
RUNNINGMEDIAN().Run();
return 0;
}
~~~