ct registration numbers).
It is guaranteed that the log is not contradictory, that is, for every visitor the types of any of his two consecutive events are distinct. Before starting the system, and after stopping the room may possibly contain visitors.
Output
Print a single integer — the minimum possible capacity of the reading room.
Sample test(s) Input
6
+ 12001
- 12001
- 1
- 1200
+ 1
+ 7
Output
3
Input
2
- 1
- 2
Output
2
Input
2
+ 1
- 1
Output
1
Note
In the first sample test, the system log will ensure that at some point in the reading room were visitors with registration numbers 1, 1200 and 12001. More people were not in the room at the same time based on the log. Therefore, the answer to the test is 3.
?
题目大意：一共n个操作，+ i表示标号为i的人进会场，－i表示标号为i的人出会场，问会场的最小容量
?
题目分析：用个set模拟一下
?
?
#include
#include
#include
using namespace std; set
st; int main() { int n, ans = 0;; scanf(%d, &n); while(n --) { char s[2]; int id; scanf(%s %d, s, &id); if(s[0] == '+') st.insert(id); //进去 else { if(!st.count(id)) //本来就在里面的出来 ans ++; else st.erase(id); //之前进去的出来 } ans = max(ans, (int) st.size()); } printf(%d , ans); }
?
?
?
?
C. Geometric Progression time limit per test：1 second memory limit per test：256 megabytes
Polycarp loves geometric progressions very much. Since he was only three years old, he loves only the progressions of length three. He also has a favorite integer k and a sequence a, consisting of n integers.
He wants to know how many subsequences of length three can be selected from a, so that they form a geometric progression with common ratio k.
A subsequence of length three is a combination of three such indexes i1,?i2,?i3, that 1?≤?i1?i2?i3?≤?n. That is, a subsequence of length three are such groups of three elements that are not necessarily consecutive in the sequence, but their indexes are strictly increasing.
A geometric progression with common ratio k is a sequence of numbers of the form b·k0,?b·k1,?...,?b·kr?-?1.
Polycarp is only three years old, so he can not calculate this number himself. Help him to do it.
Input
The first line of the input contains two integers, n and k (1?≤?n,?k?≤?2·105), showing how many numbers Polycarp's sequence has and his favorite number.
The second line contains n integers a1,?a2,?...,?an (?-?109?≤?ai?≤?109) — elements of the sequence.
Output
Output a single number — the number of ways to choose a subsequence of length three, such that it forms a geometric progression with a common ratio k.
Sample test(s) Input
5 2
1 1 2 2 4
Output
4
Input
3 1
1 1 1
Output
1
Input
10 3
1 2 6 2 3 6 9 18 3 9
Output
6
Note
In the first sample test the answer is four, as any of the two 1s can be chosen as the first element, the second element can be any of the 2s, and the third element of the subsequence must be equal to 4.
?
题目大意：n个数，问能找到多少组三个数，它们的下标严格递增且公比为k
?
题目分析：ai那么大，数组不够，直接上map，fir表示中间那个数出现的次数，sec表示第一个数出现的次数，每次按公比k找满足条件的数
?
?
#include
#include
?
?
?
?
D. One-Dimensional Battle Ships time limit per test：1 second memory limit per test：256 megabytes
Alice and Bob love playing one-dimensional battle ships. They play on the field in the form of a line consisting of n square cells (that is, on a 1?×?n table).
At the beginning of the game Alice puts k ships on the field without telling their positions to Bob. Each ship looks as a 1?×?a rectangle (that is, it occupies a sequence of a cons