TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

42.9% (6/14)

Submission's AC Ratio

22.2% (77/347)

Tags

Description

本題與桑京邀請賽完全相同,但是請小心邪惡的測資範圍和記憶體限制(當然,這裡不會有"lib1995.h"這個標頭檔)。

注意:由於本題輸入/輸出十分龐大,使用C++作答的同學,請在程式碼開頭加上#include <cstdio>,並利用scanf讀入資料、用printf輸出資料
若你使用了<iostream><bits/stdc++.h>標頭檔,極有可能會因為效率太差以致於程式執行時間、空間超過限制。
如果你需要使用<bits/stdc++.h>,請在引入該標頭檔前加上一行#define _GLIBCXX_IOSTREAM,以避免<iostream>的引入。

Input Format

輸入格式同桑京邀請賽

對於所有測資,$a_i, b_i\leq N\leq 2\times 10^ 5; M\leq 2\times 10^ 5; s_i\leq 10^ 9$。

子任務(測資) 額外限制 分數
1 (0~5) $N,M\leq 10^ 4$ 49
2 (0~11) 無限制 51

Output Format

輸出格式同桑京邀請賽

Sample Input 1

6 3
1 4
5 5
3 6
7 3 13 6 1 18

Sample Output 1

13
1
18

Hints

你有看過記憶體限制這麼小的題目嗎?如果沒有,那麼
你現在看過了(X)是不是應該要想一些比較不正常的做法呢?

Problem Source

Problem Set by Yihda Yol

Subtasks

No. Testdata Range Score
1 0~5 49
2 0~11 51

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1800 4448 262144 1 2
1 1800 4448 262144 1 2
2 1800 4448 262144 1 2
3 1800 4448 262144 1 2
4 1800 4448 262144 1 2
5 1800 4448 262144 1 2
6 1800 4448 262144 2
7 1800 4448 262144 2
8 1800 4448 262144 2
9 1800 4448 262144 2
10 1800 4448 262144 2
11 1800 4448 262144 2