Secret Sequence

아직 제출이 없습니다시간 제한1초메모리 제한1024 MB

문제

There is a secret sequence of zeros and ones of length nn, and you want to know the number of ones in the sequence. You are allowed to ask queries by giving four integers 0abcdn0 \leq a \leq b \leq c \leq d \leq n. The answer to the query will be 1-1 if the sum of the numbers at positions a,a+1,...,b1a, a+1, ..., b-1 is larger than the sum of the numbers at positions c,c+1,...,d1c, c+1, ..., d-1, and 11 if the sum is smaller. If the sums are equal, the answer will be 00.

The indices of the sequence start at 00 and end at n1n-1. Note that the intervals you're querying can be empty, if a=ba = b or c=dc = d respectively. The sum of the numbers in an empty interval is 00.

Figure out the total number of ones in the sequence using at most 200200 queries.