Description

This problem will help you understand how to use std::map.

http://en.cppreference.com/w/cpp/container/map

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

目前有五個測資，第三筆測資不算，答題測資看另外四筆

Input

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

insert: inserts a string (cmd) with the key (key) to map. If the key has already existed, insert the cmd at the begining of string (the string which the key belongs).

For example,

insert 0 "abc"

insert 1 "def"

the map should contain "abc", "def".

insert 0 "xyz"

the map should contain "xyzabc", "def".

 

range output: outputs the string from key (first) to key (last). Output a space character (' ') after printing an element.

 

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

 

operator<<: outputs all strings in map. From the smallest key to biggest key. Output a space character (' ') after printing an element.

Output

Complete insert, output, erase and operator<<.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11447.cpp

Partial Judge Header

11447.h

Discuss

Description

This problem will help you understand how to use std::set and comparator.

e.g., std::set<std::vector<int>>

http://en.cppreference.com/w/cpp/container/set

Input

How to compare the integer sequence (calculate the key of an integer sequence):

• get the length of integer sequence (size)
• key value=[first element]*(size)+[second element]*(size-1)+[third element]*(size-2)+...+[last element]*1
• compare the key value. Small key value is smaller.
• if the length of a integer sequence is 0, the key value is 0.
• e.g., the key of an integer sequence "3 9 -1 3 -6" is 48 (3*5+9*4+(-1)*3+3*2+(-6)*1)

 

The input consist of series of command. Each commands is insert, range_out or output.

​insert: inserts an integer sequence (each value is greater than -6 and smaller than 11, stop reading from cin when value is 0). If the key has already existed, then

• output "exist\n"
• erase the integer sequence from set
• reverse the integer sequence (from input)
• insert the reversed integer sequence

For example,

insert 3 9 -1 3 -6 0

The set should contain 3 9 -1 3 -6.

insert 9 -2 6 6 0

The set should contain 6 6 -2 9.

range_out: outputs all integer sequences from the integer sequence (first key) to the integer sequence (second key) of set (including the second key). First key and second key are read from input (each value is greater than -6 and smaller than 11, stop reading from cin when value is 0).

For example,

insert 2 -5 -5 0

insert 3 9 -1 3 -6 0

insert 7 6 1 2 0

insert 10 10 10 2 0

range_out -5 0 10 9 2 0

It should output

3 9 -1 3 -6

7 6 1 2

For example,

insert 2 -5 -5 0

insert 3 9 -1 3 -6 0

insert 7 6 1 2 0

insert 10 10 10 2 0

range_out -5 0 10 10 10 0

It should output

3 9 -1 3 -6

7 6 1 2

 

output: outputs all integer sequences from the smallest key to the biggest key of set. Output a space character (' ') after printing an integer. Output a newline character ('\n') after printing all elements of a key.

Output

Complete insert, range output and output.

Sample Input  Download

Sample Output  Download

Discuss

Description

Given \(N\) integers \(a_1 \dots a_N\) and \(M\) queries.
In each query, you will be given one integer \(x\), please output an integer in \(a\) which is closest to \(x\).
If there are more than one such integer, please output the smaller one.

ps. We suggest you use std::set to do this problem :)

Input

The first line contains two integers \(N, M\).
The second line contains \(N\) integers \(a_1, a_2 \dots a_N\)
Each of the next \(M\) lines contains an integer \(x\).

\(N \quad M\)
\(a_1 \quad a_2 \dots a_N\)
\(x_1\)
\(\vdots\)
\(x_M\)

Constraints

• \(1 \le N, M \le 10^5\)
  
• \(0 \le a_i, x_i \le 10^9\)

Output

Please output the answer of each query.

Sample Input  Download

Sample Output  Download

Discuss

Description

Imagine you’ve arrived at the annual NTHU Career & Recruitment Fair, where along a long corridor there are N drink booths arranged in a line from the entrance to the exit. To reflect differences in foot traffic and location value:

• Booths at the two ends (near the entrance and exit) see the most people and therefore charge higher prices.

• Mid-corridor booths have more dispersed traffic and tend to be cheaper.

• Every drink type appears at least three times, and no two booths selling the same drink ever charge the same price.

You want to quantify each drink’s popularity score based on the sequence of its prices as you walk by.

If a drink appears at booths in positions 1 ≤ i₁ < i₂ < ⋯ < i_m ≤ N with corresponding prices p₁ ​, p₂ ​, … , p_m then its popularity score is defined as max(p_u ​- p_v ​+ p_w)​ , for all u < v < w .

Intuitively, you pick three visits in chronological order—an early booth at price p_u, a middle booth at p_v, and a later booth at p_w—and compute p_u ​- p_v ​+ p_w​. Because end booths are pricier (more foot traffic) and middle booths are cheaper (less traffic), this formula captures “high-end interest” at both ends minus the mid-corridor bargain.

Note: This scoring formula does not imply that mid-corridor booths are always cheaper than end booths; it is simply one way to capture the overall trend in a drink’s popularity.

Input

The first line contains a single integer N, the total number of drink booths arranged in a line at the NTHU Career & Recruitment Fair.

The second line contains N space-separated strings s₁,s₂,…,s_N , where sis_isi​ is the name of the drink sold at booth i.

The third line contains N space-separated integers a₁,a₂,…,a_N , where aia_iai​ is the price charged by booth i.

The fourth line contains an integer Q, the number of queries you will make, and then q more lines each containing a single string T_j​ ; each T_j​​ is guaranteed to match at least one of the s_i​.

Constraints

• 1 ≤ N,Q ≤ 2 × 10⁵

• 1 ≤ | S_i |,| T_j |  ≤ 10

• 1 ≤ a_i ≤ 10⁸

^​Subtasks

• Testcases 1 ~ 3: S_i ,T_j   = "a"

• Testcases 4 ~ 6: N,Q ≤ 1000

• Testcases 7 ~ 10: No additional restrictions

^​Hints

1. Use a map<string, vector<int>> to collect, for each drink S, the list of its prices in the exact order they appear. That way each query can immediately grab the price‐sequence for its drink.
2. You want the largest p_u​ before v and the largest p_w​ after v.
   • Initialize a set suffix containing all prices for this drink.
   • Keep an empty set prefix.
   • As you scan each price p_v in order, remove p_v from suffix, if prefix and suffix are both nonempty, compute max(best,^∗prefix.rbegin()+^∗suffix.rbegin() − p_v), and then Insert p_v into prefix.
3. If the same drink is queried more than once, store its computed score in a map<string,int> ans so you only do the above scan once per drink.
4. Each drink’s price-vector is scanned once, and each insertion/erase into a balanced set costs O(log⁡ m). Overall you get O(nlog⁡n + q), which is fast enough up to 2×10⁵.

Output

For each of the Q queried drink names T_j, output on its own line the popularity score of that drink: the maximum value of p_u ​- p_v ​+ p_w over all triples of distinct occurrences u < v < w in the sequence of prices for drink T_j.

Sample Input  Download

Sample Output  Download

Discuss