Description

This is an advanced version of http://acm.cs.nthu.edu.tw/problem/11447/

Notice, this time, first and last is [first, last].

Hint: std::map<std::string,...>

lower_bound and upper_bound can help you.

Input

The input consist of series of command. Each commands is insert, sum, range output, range erase or output.

insert: inserts a integer (0<=val<65536) with a string (key) to map. If the key has already existed, insert the val at the begining of integer (the val which the key belongs).

For example,

insert a 10

insert b 20

The map should contain 10, 20.

insert a 20

The map should contain 20 10, 20.

 

sum: sums up the integer with the key. Sum is 0 if a key is not existed. Output a newline character ('\n') after printing the sum.

For example,

insert a 10

insert b 20

The map should contain 10, 20.

insert a 20

The map should contain 20 10, 20.

sum a

It should output 30 (because 20 + 10).

 

range output: outputs the integer from key (first) to key (last). Output a space character (' ') after printing an element. Output a newline character ('\n') after printing all elements (even first key equals to last key).

For example,

insert a 10

insert b 20

The map should contain 10, 20.

insert a 20

The map should contain 20 10, 20.

range output a b

It should output 2010 20.

 

range erase: erase the integer from key (first) to key (last).

 

output: outputs all integer in map. From the smallest key to biggest key. Output a space character (' ') after printing an element. Output a newline character ('\n') after printing all elements (even map is empty).

Output

Complete the above operations.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

string:

Strings are objects that represent sequences of characters.

#include <string>

begin: Return iterator to beginning

end: Return iterator to end

rbegin: Return reverse iterator to reverse beginning

rend: Return reverse iterator to reverse end

empty: Test whether container is empty

clear: Clear string

length: Return length of string

substr: Generate substring

push_back: Append character to string

pop_back: Delete last character 

 

set:

Sets are containers that store unique elements following a specific order.

#include <set>

begin: Return iterator to beginning

end: Return iterator to end

rbegin: Return reverse iterator to reverse beginning

rend: Return reverse iterator to reverse end

empty: Test whether container is empty

clear: Clear content

size: Return container size

insert: Insert element

erase: Erase elements

find: Get iterator to element

 

list:

Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions.

#include <list>

begin: Return iterator to beginning

end: Return iterator to end

rbegin: Return reverse iterator to reverse beginning

rend: Return reverse iterator to reverse end

empty: Test whether container is empty

clear: Clear content

size: Return container size

front: Access first element

back: Access last element

emplace_front: Construct and insert element at beginning

emplace_back: Construct and insert element at the end

push_front: Insert element at beginning

push_back: Insert element at the end

pop_front: Delete first element 

pop_back: Delete last element

 

vector:

Vectors are sequence containers representing arrays that can change in size.

#include <vector>

begin: Return iterator to beginning

end: Return iterator to end

rbegin: Return reverse iterator to reverse beginning

rend: Return reverse iterator to reverse end

empty: Test whether container is empty

clear: Clear content

size: Return container size

front: Access first element

back: Access last element

emplace_back: Construct and insert element at the end

push_back: Add element at the end

pop_back: Delete last element

 

queue:

#include <queue>

empty: Test whether container is empty

size: Return container size

push: Insert element

pop: remove next element

front: Access next element

 

stack:

#include <stack>

empty: Test whether container is empty

size: Return container size

top: Access next element

push: Insert element

pop: remove next element

 

map:

#include <map>

begin: Return iterator to beginning

end: Return iterator to end

rbegin: Return reverse iterator to reverse beginning

rend: Return reverse iterator to reverse end

empty: Test whether container is empty

clear: Clear content

insert: Insert Element

erase: Erase element

count : Count elements with a specific key

find: Get iterator to element

operator[]: Access element

lower_bound: Return iterator to lower bound

upper_bound: Return iterator to upper bound

 

deque:

#include <deque>

push_front: Insert element at beginning

push_back: Insert element at the end

pop_front: Delete first element 

pop_back: Delete last element

empty: Test whether container is empty

size: Return container size

insert: Insert element

erase: Erase element

operator []: Access element

front: Access first element

back: Access last element

clear: Clear the container

 

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a sequence A = a₁, a₂, ..., a_N.

A continuous subsequence A[L ... R] = a_L, ..., a_R of  A is called special if for every i, j in [L, R], a[ i ] * 2 ≠ a[ j ].

For example, if A = 3, 1, 4, 6, 2.

Then

• A[1, 3] = 3, 1, 4 is special.
• A[1, 4] = 3, 1, 4, 6 is not special because a[1] * 2 = a[4].
• A[2, 5] = 1, 4, 6, 2 is not special because a[5] * 2 = a[3] and a[2] * 2 = a[5].

 

Please find the maximum length of every special contiguous subsequence of A.

 

Input

The first line of the input contains a number T — the number of test cases.

The first line of each test case contains a positive integer N — the length of A.

The second line of each test case contains N positive integers — a₁, a₂, ..., a_N.

 

For each test,

1. T ≤ 10, N ≤ 10³, a_i ≤ 10⁹ 
2. T ≤ 10, N ≤ 10³, a_i ≤ 10⁹ 
3. T ≤ 10, N ≤ 10³, a_i ≤ 10⁹ 
4. T ≤ 10, N ≤ 10⁵, a_i ≤ 10⁹ 
5. T ≤ 10, N ≤ 10⁵, a_i ≤ 10⁹ 
6. T ≤ 10, N ≤ 10⁵, a_i ≤ 10⁹ 

 

Output

For each test case, print the maximum length of special contiguous subsequence.

 

Sample Input  Download

Sample Output  Download

Tags

Discuss