1995 . 桑京邀請賽
TopCoder
Description
一年一度的桑京邀請賽又到了！
桑京邀請賽除了比賽本身場面盛大以外，在彩券行中針對賽事的投注也十分活絡，因此猜中比賽結果所得到的彩金也非常可觀。
當地的一個彩券行針對某項的賽事推出了特殊活動。該項賽事的 $N$ 個參賽者都有自己的編號，從 $1$ 編號到 $N$。比賽結束後，每個人都會獲得一個正整數的分數，分數最高的將贏得比賽。
而這個特殊活動的內容是：下注者可以選擇一個數字區間 $[a,b]$（以下稱為「投注範圍」），並猜測編號介於 $a,b$ 之間（包含 $a,b$ ）獲得分數最高的人獲得了幾分。
這項特殊活動的彩金極多，在比賽開始前一共吸引了 $M$ 個人進行投注。然而，彩券行的電腦無法負荷如此大量的數據，光計算每個投注範圍的最高分就當機了。因此，彩券行的電腦系統負責人將所有的投注範圍和最終的比賽結果告訴了你，請你幫忙算出每個投注範圍中最高分是多少。
注意：由於本題輸入/輸出十分龐大，使用C++作答的同學，請在程式碼開頭加上#include <cstdio>，並利用scanf讀入資料、用printf輸出資料。scanf與printf的使用方式在下方Hints中有陳述。
若你使用了<iostream>或<bits/stdc++.h>標頭檔，極有可能會因為效率太差以致於程式執行時間、空間超過限制。
如果你需要使用<bits/stdc++.h>，請在引入該標頭檔前加上一行#define _GLIBCXX_IOSTREAM；或者你也可以改用#include "lib1995.h"，其中包含除了<iostream>以外的所有標頭檔。
Input Format
第一行有兩個正整數$N, M$，分別代表參加競賽的人數與投注的人數。
接下來有$M$行，每行有兩個正整數$a_i, b_i$（$a_i\leq b_i$），代表第$i$個人的投注範圍是$[a_i,b_i]$。
接下來有一行包含$N$個正整數$s_i$，代表第$i$個人在競賽中獲得的分數。
對於所有測資，$a_i, b_i\leq N\leq 2.5\times 10^ 6; M\leq 7.5\times 10^ 5; s_i\leq 10^ 9$。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~3) | $N,M\leq 10^ 4$ | 9 |
| 2 (0~7) | $N, M\leq 2\times 10^ 5$ | 21 |
| 3 (0~11) | $M\leq 5\times 10^ 5$ | 57 |
| 4 (0~14) | 無限制 | 13 |
| EXTRA (0~17) | $M\leq 10^ 6$ | 23 |
最後一個子任務為加分題。
對於該子任務，$M\leq 7.5\times 10^ 5$的限制不再適用。
Output Format
請輸出$M$行，每行有一個正整數$T_i$，代表第$i$個人的投注範圍中最高的分數。
Sample Input 1
1 4
5 5
3 6
7 3 13 6 1 18
Sample Output 1
1
18
Hints
scanf 常用的讀入方式如下：
scanf("%d",&x); 讀入一個有號整數至int 型態變數x。
scanf("%lld",&y); 讀入一個有號整數至long long 型態變數y。
scanf("%u",&x); 讀入一個無號整數至unsigned int 型態變數x。
scanf("%llu",&y); 讀入一個無號整數至unsigned long long 型態變數y。
printf 常用的輸出方式如下：
printf("%d\n",x); 輸出一行包含一個int 型態變數x。
printf("%lld\n",y); 輸出一行包含一個long long 型態變數y。
printf("%u\n",x); 輸出一行包含一個unsigned int 型態變數x。
printf("%llu\n",y); 輸出一行包含一個unsigned long long 型態變數y。
Problem Source
Problem Set by Yihda Yol
建國中學106學年度校隊選拔：複試pE
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~3 | 9 |
| 2 | 0~7 | 21 |
| 3 | 0~11 | 57 |
| 4 | 0~14 | 13 |
| 5 | 0~17 | 23 |