1000ms

65536kB

You are given an easy task by your supervisor -- to find the best value of X, one of the parameters in an evaluation function, in order to improve the accuracy of the whole program.However, after a few days' analysis, you realize that it is far harder than you imagine. There are so many values X can be, and the only way to find the best one among them is to try all these possible values one after another!Fortunately, you know that X is an integer and thanks to the previous works by your senior fellow apprentices, you have got n constraints on X. Each constraint must be in one of the following forms:
1. < k: means that X is less than integer k;
2. > k: means that X is greater than integer k;
3. <= k: means that X is less than or equal to integer k;
4. >= k: means that X is greater than or equal to integer k;
5. = k: means that X is equal to integer k.Now, you are going to figure out how many possible values X can be, so that you can estimate whether it is possible to finish your task before deadline.

The first line contains an integer T (1 ≤ T ≤ 10) -- the number of test cases.For each test case:
The first line contains an integer n. 0 ≤ n ≤ 10 000.
Then follows n lines, each line contains a comparison operator o and an integer k, separated by a single space. o can be one of “>”, “<”, “>=”, “<=”, and “=”. 0 ≤ | k | ≤ 1 000 000 000.
There is no contradictory between these constraints, in other word, at least one integer value meets all of them.

For each test case, output one integer in a single line -- the number of possible values of X, or “-1” if the answer is infinite.

```1
2
> 2
<= 5
```

`3`
```#include <iostream>
#include <stdio.h>
#include <string>
#define inf 1000000001
using namespace std;
int main()
{
int T,n;
int a,b,x;
string str;
cin>>T;
while(T--) {
cin>>n;
a = -inf;
b = inf;
while(n--) {
cin>>str>>x;
if(str == ">") {
if(x +1 > a)
a = x+1;
}
else if(str == ">=") {
if(x > a)
a = x;
}
else if(str == "<") {
if(x - 1 < b)
b = x-1;
}
else if(str == "<="){
if(x < b)
b = x;
}
else{ //"="
if(x >= a && x <=b){
a = x;
b = x;
}
else
a = b + 1;
}
}
if(a == -inf || b == inf || b - a < 0)
cout<<-1<<endl;
else
cout<<b -a +1 <<endl;
}
return 0;
}
```