Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
整数 L,R と、英小文字のみからなる文字列 S が与えられます。
S の L 文字目から R 文字目までの部分を反転した(すなわち、 L 文字目から R 文字目までの文字の並びを逆にした)文字列を出力してください。
制約
- S は英小文字のみからなる。
- 1 \le |S| \le 10^5 (|S| は S の長さ)
- L,R は整数
- 1 \le L \le R \le |S|
入力
入力は以下の形式で標準入力から与えられる。
L R S
出力
問題文の指示通り出力せよ。
入力例 1
3 7 abcdefgh
出力例 1
abgfedch
abcdefgh の 3 文字目から 7 文字目までの部分を反転すると、 abgfedch となります。
入力例 2
1 7 reviver
出力例 2
reviver
操作を行った結果が元の文字列と同一であることもあります。
入力例 3
4 13 merrychristmas
出力例 3
meramtsirhcyrs
Score : 200 points
Problem Statement
You are given integers L, R, and a string S consisting of lowercase English letters.
Print this string after reversing (the order of) the L-th through R-th characters.
Constraints
- S consists of lowercase English letters.
- 1 \le |S| \le 10^5 (|S| is the length of S.)
- L and R are integers.
- 1 \le L \le R \le |S|
Input
Input is given from Standard Input in the following format:
L R S
Output
Print the specified string.
Sample Input 1
3 7 abcdefgh
Sample Output 1
abgfedch
After reversing the 3-rd through 7-th characters of abcdefgh, we have abgfedch.
Sample Input 2
1 7 reviver
Sample Output 2
reviver
The operation may result in the same string as the original.
Sample Input 3
4 13 merrychristmas
Sample Output 3
meramtsirhcyrs
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
座標平面上に N 枚の長方形のシートが張られています。
各シートが覆う長方形領域の各辺はそれぞれ x 軸または y 軸と平行であり、
具体的には、i 枚目のシートはちょうど A_i \leq x\leq B_i かつ C_i \leq y\leq D_i をみたす領域全体を覆っています。
1 枚以上のシートによって覆われている領域 の面積を S とすると、
S は制約の条件下で整数となる事が証明できます。
S を整数の形で出力してください。
制約
- 2\leq N\leq 100
- 0\leq A_i<B_i\leq 100
- 0\leq C_i<D_i\leq 100
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 C_1 D_1 A_2 B_2 C_2 D_2 \vdots A_N B_N C_N D_N
出力
1 枚以上のシートによって覆われている領域の面積 S を整数で出力せよ。
入力例 1
3 0 5 1 3 1 4 0 5 2 5 2 4
出力例 1
20
3 枚のシートによって覆われている領域は次のようになります。
ここで、赤色・黄色・青色はそれぞれ 1 枚目・ 2 枚目・ 3 枚目のシートによって覆われている領域を表しています。

よって、1 枚以上のシートによって覆われている領域の面積は S=20 となります。
入力例 2
2 0 100 0 100 0 100 0 100
出力例 2
10000
異なるシートが同じ領域を覆っている事があることに注意してください。
入力例 3
3 0 1 0 1 0 3 0 5 5 10 0 10
出力例 3
65
Score : 200 points
Problem Statement
There are N rectangular sheets spread out on a coordinate plane.
Each side of the rectangular region covered by each sheet is parallel to the x- or y-axis.
Specifically, the i-th sheet covers exactly the region satisfying A_i \leq x\leq B_i and C_i \leq y\leq D_i.
Let S be the area of the region covered by one or more sheets. It can be proved that S is an integer under the constraints.
Print S as an integer.
Constraints
- 2\leq N\leq 100
- 0\leq A_i<B_i\leq 100
- 0\leq C_i<D_i\leq 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 B_1 C_1 D_1 A_2 B_2 C_2 D_2 \vdots A_N B_N C_N D_N
Output
Print the area S of the region covered by one or more sheets as an integer.
Sample Input 1
3 0 5 1 3 1 4 0 5 2 5 2 4
Sample Output 1
20
The three sheets cover the following regions.
Here, red, yellow, and blue represent the regions covered by the first, second, and third sheets, respectively.

Therefore, the area of the region covered by one or more sheets is S=20.
Sample Input 2
2 0 100 0 100 0 100 0 100
Sample Output 2
10000
Note that different sheets may cover the same region.
Sample Input 3
3 0 1 0 1 0 3 0 5 5 10 0 10
Sample Output 3
65
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。
長さ M の A の連続部分列 B=(B_1,B_2,\dots,B_M) に対する、\displaystyle \sum_{i=1}^{M} i \times B_i の最大値を求めてください。
注記
数列の連続部分列とは、数列の先頭から 0 個以上、末尾から 0 個以上の要素を削除して得られる列のことをいいます。
例えば (2, 3) や (1, 2, 3) は (1, 2, 3, 4) の連続部分列ですが、(1, 3) や (3,2,1) は (1, 2, 3, 4) の連続部分列ではありません。
制約
- 1 \le M \le N \le 2 \times 10^5
- - 2 \times 10^5 \le A_i \le 2 \times 10^5
- 入力は全て整数。
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \dots A_N
出力
答えを出力せよ。
入力例 1
4 2 5 4 -1 8
出力例 1
15
B=(A_3,A_4) とした場合、\displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times (-1) + 2 \times 8 = 15 となります。16 以上の値を達成することはできないため、解は 15 です。
B=(A_1,A_4) などを選ぶことができないことに注意してください。
入力例 2
10 4 -3 1 -4 1 -5 9 -2 6 -5 3
出力例 2
31
Score : 300 points
Problem Statement
You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N.
Find the maximum value of \displaystyle \sum_{i=1}^{M} i \times B_i for a contiguous subarray B=(B_1,B_2,\dots,B_M) of A of length M.
Notes
A contiguous subarray of a number sequence is a sequence that is obtained by removing 0 or more initial terms and 0 or more final terms from the original number sequence.
For example, (2, 3) and (1, 2, 3) are contiguous subarrays of (1, 2, 3, 4), but (1, 3) and (3,2,1) are not contiguous subarrays of (1, 2, 3, 4).
Constraints
- 1 \le M \le N \le 2 \times 10^5
- - 2 \times 10^5 \le A_i \le 2 \times 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
4 2 5 4 -1 8
Sample Output 1
15
When B=(A_3,A_4), we have \displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times (-1) + 2 \times 8 = 15. Since it is impossible to achieve 16 or a larger value, the solution is 15.
Note that you are not allowed to choose, for instance, B=(A_1,A_4).
Sample Input 2
10 4 -3 1 -4 1 -5 9 -2 6 -5 3
Sample Output 2
31
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
りんご市場に N 人の売り手と M 人の買い手がいます。
i 番目の売り手は、A_i 円以上でならりんごを売ってもよいと考えています。
i 番目の買い手は、B_i 円以下でならりんごを買ってもよいと考えています。
次の条件を満たすような最小の整数 X を求めてください。
条件:りんごを X 円で売ってもよいと考える売り手の人数が、りんごを X 円で買ってもよいと考える買い手の人数以上である。
制約
- 1 \leq N,M \leq 2\times 10^5
- 1\leq A_i,B_i \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 \ldots A_N B_1 \ldots B_M
出力
答えを出力せよ。
入力例 1
3 4 110 90 120 100 80 120 10000
出力例 1
110
りんごを 110 円で売ってもよいと考える売り手は 1,2 番目の 2 人であり、りんごを 110 円で買ってもよいと考える買い手は 3,4 番目の 2 人であるため、110 は条件を満たします。
110 未満の整数が条件を満たすことはないため、これが答えです。
入力例 2
5 2 100000 100000 100000 100000 100000 100 200
出力例 2
201
入力例 3
3 2 100 100 100 80 120
出力例 3
100
Score : 300 points
Problem Statement
There are N sellers and M buyers in an apple market.
The i-th seller may sell an apple for A_i yen or more (yen is the currency in Japan).
The i-th buyer may buy an apple for B_i yen or less.
Find the minimum integer X that satisfies the following condition.
Condition: The number of people who may sell an apple for X yen is greater than or equal to the number of people who may buy an apple for X yen.
Constraints
- 1 \leq N,M \leq 2\times 10^5
- 1\leq A_i,B_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 \ldots A_N B_1 \ldots B_M
Output
Print the answer.
Sample Input 1
3 4 110 90 120 100 80 120 10000
Sample Output 1
110
Two sellers, the 1-st and 2-nd, may sell an apple for 110 yen; two buyers, the 3-rd and 4-th, may buy an apple for 110 yen. Thus, 110 satisfies the condition.
Since an integer less than 110 does not satisfy the condition, this is the answer.
Sample Input 2
5 2 100000 100000 100000 100000 100000 100 200
Sample Output 2
201
Sample Input 3
3 2 100 100 100 80 120
Sample Output 3
100
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
整数 N が与えられます。以下の条件を満たす N 以下の正整数の組 (i,j) の個数を求めてください。
- i \times j は平方数である。
制約
- 1 \le N \le 2 \times 10^5
- N は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
4
出力例 1
6
(1,1),(1,4),(2,2),(3,3),(4,1),(4,4) の 6 個が条件を満たします。
(2,3) は 2 \times 3 =6 が平方数でないため条件を満たしません。
入力例 2
254
出力例 2
896
Score : 400 points
Problem Statement
You are given an integer N. Find the number of pairs (i,j) of positive integers at most N that satisfy the following condition:
- i \times j is a square number.
Constraints
- 1 \le N \le 2 \times 10^5
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
4
Sample Output 1
6
The six pairs (1,1),(1,4),(2,2),(3,3),(4,1),(4,4) satisfy the condition.
On the other hand, (2,3) does not, since 2 \times 3 =6 is not a square number.
Sample Input 2
254
Sample Output 2
896