AtCoder Regular Contest 066

C - Lining Up

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

1～N までの番号がついた、N 人の人がいます。彼らは昨日、ある順番で左右一列に並んでいましたが、今日になってその並び方が分からなくなってしまいました。しかし、彼らは全員、「自分の左に並んでいた人数と自分の右に並んでいた人数の差の絶対値」を覚えています。彼らの報告によると、人 i の、「自分の左に並んでいた人数と自分の右に並んでいた人数の差の絶対値」は A_i です。

彼らの報告を元に、元の並び方が何通りあり得るかを求めてください。ただし、答えは非常に大きくなることがあるので、10^9+7 で割った余りを出力してください。また、彼らの報告が間違っており、ありうる並び方がないこともありえます。その際は 0 を出力してください。

制約

1≦N≦10^5
0≦A_i≦N-1

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 ... A_N

出力

元の並び順としてありうるものが何通りあるか求め、10^9+7 で割った余りを出力せよ。

入力例 1

5
2 4 4 0 2

出力例 1

ありうる並び方は、人の番号で書くと、

2,1,4,5,3
2,5,4,1,3
3,1,4,5,2
3,5,4,1,2

の 4 通りです。

入力例 2

7
6 4 0 2 4 0 2

出力例 2

どのような並び方でも、報告と矛盾するので、0 が答えになります。

入力例 3

8
7 5 1 1 7 3 5 3

出力例 3

Score : 300 points

Problem Statement

There are N people, conveniently numbered 1 through N. They were standing in a row yesterday, but now they are unsure of the order in which they were standing. However, each person remembered the following fact: the absolute difference of the number of the people who were standing to the left of that person, and the number of the people who were standing to the right of that person. According to their reports, the difference above for person i is A_i.

Based on these reports, find the number of the possible orders in which they were standing. Since it can be extremely large, print the answer modulo 10^9+7. Note that the reports may be incorrect and thus there may be no consistent order. In such a case, print 0.

Constraints

1≦N≦10^5
0≦A_i≦N-1

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the number of the possible orders in which they were standing, modulo 10^9+7.

Sample Input 1

5
2 4 4 0 2

Sample Output 1

There are four possible orders, as follows:

2,1,4,5,3
2,5,4,1,3
3,1,4,5,2
3,5,4,1,2

Sample Input 2

7
6 4 0 2 4 0 2

Sample Output 2

Any order would be inconsistent with the reports, thus the answer is 0.

Sample Input 3

8
7 5 1 1 7 3 5 3

Sample Output 3

D - Xor Sum

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 600 点

問題文

正の整数 N が与えられます。 2 つの整数 u,v(0≦u,v≦N) であって、ある非負整数 a,b が存在して、a xor b=u、a+b=v となるようなものが何通りあるかを求めてください。ここで、xor はビットごとの排他的論理和を表します。なお、答えは非常に大きくなることがあるので、10^9+7 で割った余りを求めてください。

制約

1≦N≦10^{18}

入力

入力は以下の形式で標準入力から与えられる。

出力

ありうる 2 数の組が何通りあるかを求め、10^9+7 で割った余りを出力せよ。

入力例 1

出力例 1

u,v としてありうるものは、以下の 5 通りです。

u=0,v=0（ a=0,b=0 とすると、0 xor 0=0、0+0=0 となります。）
u=0,v=2（ a=1,b=1 とすると、1 xor 1=0、1+1=2 となります。）
u=1,v=1（ a=1,b=0 とすると、1 xor 0=1、1+0=1 となります。）
u=2,v=2（ a=2,b=0 とすると、2 xor 0=2、2+0=2 となります。）
u=3,v=3（ a=3,b=0 とすると、3 xor 0=3、3+0=3 となります。）

入力例 2

出力例 2

入力例 3

1000000000000000000

出力例 3

787014179

Score : 600 points

Problem Statement

You are given a positive integer N. Find the number of the pairs of integers u and v (0≦u,v≦N) such that there exist two non-negative integers a and b satisfying a xor b=u and a+b=v. Here, xor denotes the bitwise exclusive OR. Since it can be extremely large, compute the answer modulo 10^9+7.

Constraints

1≦N≦10^{18}

Input

The input is given from Standard Input in the following format:

Output

Print the number of the possible pairs of integers u and v, modulo 10^9+7.

Sample Input 1

Sample Output 1

The five possible pairs of u and v are:

u=0,v=0 (Let a=0,b=0, then 0 xor 0=0, 0+0=0.)
u=0,v=2 (Let a=1,b=1, then 1 xor 1=0, 1+1=2.）
u=1,v=1 (Let a=1,b=0, then 1 xor 0=1, 1+0=1.）
u=2,v=2 (Let a=2,b=0, then 2 xor 0=2, 2+0=2.）
u=3,v=3 (Let a=3,b=0, then 3 xor 0=3, 3+0=3.）

Sample Input 2

Sample Output 2

Sample Input 3

1000000000000000000

Sample Output 3

787014179

E - Addition and Subtraction Hard

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 900 点

問題文

joisinoお姉ちゃんは、N 項から成る式、A_1 op_1 A_2 ... op_{N-1} A_N を持っています。ここで、A_i は整数で、op_i は、+ または - の記号です。 joisinoお姉ちゃんは大きい数が好きなので、括弧を好きな数だけ( 0 個でもよい)挿入することで、計算の順番を変え、式の値を最大化したいです。開き括弧は数の直前、閉じ括弧は数の直後にのみ、挿入することが許されます。同じ場所に挿入する括弧の個数に制限はありません。あなたの仕事は、式に括弧をいくつか挿入した際に、式の値としてありうるものの最大値を求めるプログラムを作ることです。

制約

1≦N≦10^5
1≦A_i≦10^9
op_i は、+ または - の記号である。

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 op_1 A_2 ... op_{N-1} A_N

出力

括弧をいくつか挿入してできる式の値としてありうるものの最大値を出力せよ。

入力例 1

3
5 - 1 - 3

出力例 1

5 - (1 - 3) = 7 となり、これが最大なので、7 を出力します。

入力例 2

5
1 - 2 + 3 - 4 + 5

出力例 2

1 - (2 + 3 - 4) + 5 = 5 となり、これが最大なので、5 を出力します。

入力例 3

5
1 - 20 - 13 + 14 - 5

出力例 3

1 - (20 - (13 + 14) - 5) = 13 となり、これが最大なので、13 を出力します。

Score : 900 points

Problem Statement

Joisino has a formula consisting of N terms: A_1 op_1 A_2 ... op_{N-1} A_N. Here, A_i is an integer, and op_i is an binary operator either + or -. Because Joisino loves large numbers, she wants to maximize the evaluated value of the formula by inserting an arbitrary number of pairs of parentheses (possibly zero) into the formula. Opening parentheses can only be inserted immediately before an integer, and closing parentheses can only be inserted immediately after an integer. It is allowed to insert any number of parentheses at a position. Your task is to write a program to find the maximum possible evaluated value of the formula after inserting an arbitrary number of pairs of parentheses.

Constraints

1≦N≦10^5
1≦A_i≦10^9
op_i is either + or -.

Input

The input is given from Standard Input in the following format:

N
A_1 op_1 A_2 ... op_{N-1} A_N

Output

Print the maximum possible evaluated value of the formula after inserting an arbitrary number of pairs of parentheses.

Sample Input 1

3
5 - 1 - 3

Sample Output 1

The maximum possible value is: 5 - (1 - 3) = 7.

Sample Input 2

5
1 - 2 + 3 - 4 + 5

Sample Output 2

The maximum possible value is: 1 - (2 + 3 - 4) + 5 = 5.

Sample Input 3

5
1 - 20 - 13 + 14 - 5

Sample Output 3

The maximum possible value is: 1 - (20 - (13 + 14) - 5) = 13.

F - Contest with Drinks Hard

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 1400 点

問題文

joisinoお姉ちゃんは、あるプログラミングコンテストの決勝を控えています。このコンテストでは、N 問の問題が用意されており、それらには 1～N の番号がついています。 joisinoお姉ちゃんは、問題 i(1≦i≦N) を解くのにかかる時間が T_i 秒であることを知っています。

このコンテストでは、コンテスタントはまず最初に、これから解く問題をいくつか選びます。次にそれらの問題を解き、すべて解き終わると、スコアの計算が行われます。このコンテストでのスコアの計算方法は特殊であり、具体的には、以下の式で計算されます。

スコア = 「整数の組 L,R(1≦L≦R≦N) であって、L≦i≦R を満たす全ての i について、問題 i が解かれているようなもの」の個数 ー 問題を解くのに要した時間の合計

なお、問題を 1 つも解かないことも許され、その際のスコアは 0 になります。

また、このコンテストでは、M 種類のドリンクが提供されており、1～M の番号がついています。そして、ドリンク i(1≦i≦M) を飲むと、脳が刺激され、問題 P_i を解くのにかかる時間が X_i 秒になります。なお、X_i が、もともと問題 P_i を解くのに要する時間より長いこともありえます。他の問題を解くのにかかる時間に変化はありません。

コンテスタントは、コンテスト開始前にいずれかのドリンクを 1 本だけ飲むことができます。そこでjoisinoお姉ちゃんは、それぞれのドリンクについて、それを飲んだ際に、コンテストで取ることのできる最大スコアを知りたいと思いました。あなたの仕事は、joisinoお姉ちゃんの代わりにこれを求めるプログラムを作成することです。

制約

入力は全て整数である
1≦N≦3*10^5
1≦T_i≦10^9
T_i の総和 ≦10^{12}
1≦M≦3*10^5
1≦P_i≦N
1≦X_i≦10^9

入力

入力は以下の形式で標準入力から与えられる。

N
T_1 T_2 ... T_N
M
P_1 X_1
P_2 X_2
:
P_M X_M

出力

それぞれのドリンクについて、それを飲んだ際の最大スコアを求め、順番に 1 行ずつ出力せよ。

入力例 1

出力例 1

9
2

1 番目のドリンクを飲んだ場合、全ての問題を解くことで最大スコアが得られます。

2 番目のドリンクを飲んだ場合、1,2,4,5 番目の問題を解くことで最大スコアが得られます。

入力例 2

12
1 2 1 3 4 1 2 1 12 3 12 12
10
9 3
11 1
5 35
6 15
12 1
1 9
4 3
10 2
5 1
7 6

出力例 2

Score : 1400 points

Problem Statement

Joisino is about to compete in the final round of a certain programming competition. In this contest, there are N problems, numbered 1 through N. Joisino knows that it takes her T_i seconds to solve problem i(1≦i≦N).

In this contest, a contestant will first select some number of problems to solve. Then, the contestant will solve the selected problems. After that, the score of the contestant will be calculated as follows:

(The score) = (The number of the pairs of integers L and R (1≦L≦R≦N) such that for every i satisfying L≦i≦R, problem i is solved) - (The total number of seconds it takes for the contestant to solve the selected problems)

Note that a contestant is allowed to choose to solve zero problems, in which case the score will be 0.

Also, there are M kinds of drinks offered to the contestants, numbered 1 through M. If Joisino takes drink i(1≦i≦M), her brain will be stimulated and the time it takes for her to solve problem P_i will become X_i seconds. Here, X_i may be greater than the length of time originally required to solve problem P_i. Taking drink i does not affect the time required to solve the other problems.

A contestant is allowed to take exactly one of the drinks before the start of the contest. For each drink, Joisino wants to know the maximum score that can be obtained in the contest if she takes that drink. Your task is to write a program to calculate it instead of her.

Constraints

All input values are integers.
1≦N≦3*10^5
1≦T_i≦10^9
(The sum of T_i) ≦10^{12}
1≦M≦3*10^5
1≦P_i≦N
1≦X_i≦10^9

Input

The input is given from Standard Input in the following format:

N
T_1 T_2 ... T_N
M
P_1 X_1
P_2 X_2
:
P_M X_M

Output

For each drink, print the maximum score that can be obtained if Joisino takes that drink, in order, one per line.

Sample Input 1

Sample Output 1

9
2

If she takes drink 1, the maximum score can be obtained by solving all the problems.

If she takes drink 2, the maximum score can be obtained by solving the problems 1,2,4 and 5.

Sample Input 2

12
1 2 1 3 4 1 2 1 12 3 12 12
10
9 3
11 1
5 35
6 15
12 1
1 9
4 3
10 2
5 1
7 6

Sample Output 2