You are a trader at an investment company. One day, you discover that the stock you're responsible for trading follows an exactly repeating daily pattern: the day is divided into $$$n$$$ equal time intervals, and the stock's price during the $$$i$$$-th interval is always $$$a_i$$$. As the $$$n$$$-th interval of one day concludes, the first interval of the next day immediately follows, with the price shifting from $$$a_n$$$ to $$$a_1$$$. This is a once-in-a-lifetime opportunity — if you can just buy and sell according to this pattern you've already figured out, during your working hours, there's a guaranteed way to profit!
Your working hours vary, and a working period may extend past midnight. You are given $$$q$$$ working periods. The $$$i$$$-th period starts at slot $$$l_i$$$ and ends at slot $$$r_i$$$, including both endpoints. The slots in chronological order are:
- $$$l_i,l_i+1,\ldots,r_i$$$ if $$$l_i\le r_i$$$;
- $$$l_i,l_i+1,\ldots,n,1,2,\ldots,r_i$$$ if $$$l_i \gt r_i$$$.
In each working period, you may complete at most $$$k$$$ transactions. Each transaction consists of buying one share and selling it in a later time slot, with profit equal to the sale price minus the purchase price. You may hold at most one share at a time, so you must sell your current share before buying another. All purchases and sales must take place within that working period and follow the chronological order above. You may also make no transactions, earning a profit of $$$0$$$.
For each working period, independently find the maximum total profit you can earn.
The first line contains three integers $$$n,k,q$$$ ($$$1\le n\le 10^5$$$, $$$1\le k\le 800$$$, $$$1\le q\le 3\times 10^5$$$): the number of time slots in a day, the maximum number of transactions per working period, and the number of working periods, respectively.
The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le 10^6$$$), where $$$a_i$$$ is the stock price in the $$$i$$$-th time slot of each day.
Each of the next $$$q$$$ lines contains two integers $$$l_i,r_i$$$ ($$$1\le l_i,r_i\le n$$$), describing the $$$i$$$-th working period.
Let $$$\text{len}_i$$$ be the number of time slots in this period. If $$$l_i\le r_i$$$, then $$$\text{len}_i=r_i-l_i+1$$$; otherwise, $$$\text{len}_i=n-l_i+1+r_i$$$.
For each working period, $$$l_i$$$ and $$$\text{len}_i$$$ are generated independently and uniformly at random from $$$[1,n]$$$ and $$$\left[\max(1,\lfloor 0.15n\rfloor),\ \max(1,\lfloor 0.85n\rfloor)\right]$$$, respectively. The value of $$$r_i$$$ is uniquely determined by $$$l_i$$$ and $$$\text{len}_i$$$. Specifically, when the interval is $$$[1,1]$$$, the random result will always be $$$1$$$.
There are exactly $$$50$$$ test cases, excluding the sample.
Output $$$q$$$ lines. The $$$i$$$-th line should contain one integer: the maximum profit you can earn during the $$$i$$$-th working period with at most $$$k$$$ transactions.
6 2 33 1 4 1 5 92 55 24 4
7 4 0
You have a fair six-sided die with positive integer face values $$$a_1,a_2,\ldots,a_6$$$. Construct another fair six-sided die with positive integer face values $$$b_1,b_2,\ldots,b_6$$$ whose sum is exactly $$$k$$$. Face values may repeat on either die.
Roll each die once, independently. The new die wins if and only if its value is strictly greater than the original die's value; a tie is not a win. Determine whether you can make it win at least $$$19$$$ of the $$$36$$$ equally likely pairs of faces (that is, with probability strictly greater than $$$50\%$$$). If so, construct such a die.
The first line contains six integers $$$a_1,a_2,\ldots,a_6$$$ ($$$1\le a_i\le 10^9$$$), the labels of the original die.
The second line contains an integer $$$k$$$ ($$$1\le k\le 10^{18}$$$), the required sum of the new die's labels.
If no valid new die exists, print NO.
Otherwise, print YES on the first line and six positive integers $$$b_1,b_2,\ldots,b_6$$$ on the second line. Their sum must be exactly $$$k$$$, and the new die must win at least $$$19$$$ of the $$$36$$$ pairs of faces.
The labels may appear in any order. If multiple answers exist, print any one. The strings YES and NO are case-sensitive.
1 2 3 4 5 625
YES 1 1 2 7 7 7
1 1 1 1 1 19
NO
For the first example, another valid choice of labels is $$$5,4,4,4,4,4$$$. These labels sum to $$$5+4+4+4+4+4=25$$$. Its face labeled $$$5$$$ beats four faces of the original die, and each face labeled $$$4$$$ beats three. Thus, it wins $$$4+5\cdot3=19$$$ pairs.
In the second example, a face must be labeled at least $$$2$$$ to win. Each such face wins six pairs, so at least four are needed to win $$$19$$$ pairs. Even if the other two faces are labeled $$$1$$$, the sum is at least $$$2+2+2+2+1+1=10 \gt 9$$$.
EPS.AC is the problem-setting team for this contest. Its members are Colin, Claris, and Little_Sheep_Yawn.
They have prepared $$$n$$$ candidate problems for this contest. Each member ranks the $$$n$$$ problems from easiest to hardest according to their own judgment. To balance the contest's difficulty and distinguish contestants of different levels, they want to divide these problems into difficulty tiers, ordered from easiest to hardest. Every problem must belong to exactly one tier. Problems within the same tier are not ordered by difficulty, and each tier must contain at least one problem.
Arrange the tiers from left to right, from easiest to hardest. For a boundary between two consecutive tiers, the left side contains all problems in the tiers before it, and the right side contains all problems in the tiers after it. A member supports this boundary if every problem on its left appears before every problem on its right in that member's ranking.
A division into tiers is valid if every boundary has the support of at least two members. Different boundaries may have different supporters.
More difficulty tiers mean better problem setting. To help them create a good contest, find the maximum possible number of tiers.
The input contains multiple test cases. The first line contains an integer $$$t~(1\le t\le 2\times 10^5)$$$, the number of test cases.
For each test case:
- The first line contains an integer $$$n~(1\le n\le 2\times 10^5)$$$.
- Each of the next three lines contains a permutation of $$$1,2,\ldots,n$$$, giving the rankings of Colin, Claris, and Little_Sheep_Yawn, respectively.
It is guaranteed that the sum of $$$n$$$ over all test cases is at most $$$2\times 10^5$$$.
For each test case, print the maximum possible number of tiers.
362 1 4 5 6 31 2 3 4 5 63 1 4 2 6 541 3 2 41 2 4 32 1 3 431 2 32 3 13 1 2
3 4 1
In the first test case, the problems can be divided into three tiers $$$\{1,2\},\{3,4\},\{5,6\}$$$, listed from easiest to hardest. Colin and Claris support the first boundary, while Claris and Little_Sheep_Yawn support the second. This division is optimal.
In the second test case, each of the four problems can form its own tier, ordered from easiest to hardest as $$$\{1\},\{2\},\{3\},\{4\}$$$. The three boundaries are supported by Colin and Claris, by Claris and Little_Sheep_Yawn, and by Colin and Little_Sheep_Yawn, respectively.
In the third test case, no boundary is valid, so all problems must be placed in a single tier.
You need to guide a night butterfly through the darkness. Its starting point is the common center of six radial tracks, numbered clockwise from $$$0$$$ to $$$5$$$. Track $$$0$$$ is the main track; the other five are auxiliary tracks.
Only certain intervals on the tracks are lit. The main track has one set of lit intervals, while all five auxiliary tracks share another set. All lit intervals are closed, and their endpoints represent distances from the center.
Before each flight, you may choose a positive real speed $$$d$$$, which remains fixed throughout the flight. The butterfly starts at the center at time $$$0$$$. At every positive integer time $$$t$$$, it is on track $$$(t\bmod 6)$$$ at a distance $$$t\cdot d$$$ from the center. Thus, it visits tracks $$$1,2,3,4,5,0,1,2,\ldots$$$ in this order.
You are given $$$q$$$ queries, each specifying a target distance $$$T$$$. You want the butterfly to reach the main track at some time $$$k$$$, at a distance $$$T$$$ from the center. Thus, $$$k$$$ must be a positive multiple of $$$6$$$, and $$$k\cdot d=T$$$. At every integer time $$$1,2,\ldots,k$$$, the butterfly must be within a lit interval on its current track, or it will fall into darkness and lose its way. There are no restrictions at other times, including time $$$0$$$.
For each query, find the earliest time $$$k$$$ at which the butterfly can safely reach its target, or print -1 if it cannot. The queries are independent, and you may choose $$$d$$$ separately for each query.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n,m\le50$$$), representing the numbers of lit intervals on the main track and in the set shared by all five auxiliary tracks, respectively.
Each of the next $$$n$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1\le l\le r\le10^{18}$$$), representing a lit interval $$$[l,r]$$$ on the main track.
Each of the next $$$m$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1\le l\le r\le10^{18}$$$), representing a lit interval $$$[l,r]$$$ shared by all five auxiliary tracks.
Within each set, the intervals are pairwise disjoint and are given in increasing order of their left endpoints. In particular, consecutive intervals satisfy $$$l_{i+1} \gt r_i$$$.
The next line contains an integer $$$q$$$ ($$$1\le q\le100$$$), representing the number of queries.
Each of the next $$$q$$$ lines contains an integer $$$T$$$ ($$$1\le T\le10^{18}$$$), representing the target distance of one query.
For each query, print on a separate line the earliest time $$$k$$$ at which the butterfly can safely reach its target, or -1 if it cannot.
2 26 612 121 57 11361218
6 12 -1
For $$$T=6$$$, choosing $$$d=1$$$ lets the butterfly reach the target at time $$$k=6$$$. The distances at the first five integer times are $$$1,2,3,4,5$$$, all in the lit interval $$$[1,5]$$$ on the auxiliary tracks. At the sixth integer time, the distance is $$$6$$$, which is in the lit interval $$$[6,6]$$$ on the main track.
For $$$T=12$$$, choosing $$$d=1$$$ lets the butterfly reach the target at time $$$k=12$$$. Its distances while on the auxiliary tracks are all in $$$[1,5]\cup[7,11]$$$, while its distances on the main track are $$$6$$$ and $$$12$$$. To arrive at time $$$k=6$$$, it would need $$$d=2$$$, but then at time $$$3$$$ it would be at an unsafe position at distance $$$6$$$ from the center on an auxiliary track.
The diagrams below show the query $$$T=12$$$. The first two use $$$d=1$$$, and the third uses $$$d=2$$$. Gold segments and points are lit intervals. Dark blue dots are labeled with their times, and the red cross marks a position in darkness. The second panel continues from the hollow dot at time $$$6$$$. Dashed arrows show only the order of integer-time positions, not the actual flight path between them.
For $$$T=18$$$, the target is outside every lit interval on the main track, so it cannot be reached safely.
For a permutation of $$$1,2,\ldots,n$$$, let $$$s_i$$$ be the length of the shortest contiguous subarray containing all values $$$1,2,\ldots,i$$$.
Let $$$\operatorname{pos}_p(x)$$$ be the position of $$$x$$$ in the permutation; we have
$$$$$$ s_i=\max_{1\le x\le i}\operatorname{pos}_p(x)-\min_{1\le x\le i}\operatorname{pos}_p(x)+1. $$$$$$
For each $$$i$$$, an interval constraint $$$[l_i,r_i]$$$ is given.
Please count the permutations satisfying $$$l_i\le s_i\le r_i$$$ for every $$$i$$$. Print the answer modulo $$$998244353$$$.
The first line contains an integer $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$).
Each of the next $$$n$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$).
Print the number of valid permutations modulo $$$998244353$$$.
Please note that a valid permutation may not exist.
31 12 23 3
4
The valid permutations in the example are $$$(1,2,3)$$$, $$$(2,1,3)$$$, $$$(3,1,2)$$$, and $$$(3,2,1)$$$.
This is a communication problem. Your program will be run twice for each test, in two independent processes.
First Run
You are given a permutation $$$p=(p_1,p_2,\ldots,p_n)$$$ of $$$1,2,\ldots,n$$$.
Output an $$$n\times n$$$ matrix $$$A$$$ such that each row is a permutation of $$$1,2,\ldots,n$$$ and all rows are pairwise distinct.
Second Run
Before the second run, the judge randomly shuffles the rows of $$$A$$$ to obtain a matrix $$$B$$$. The order of the elements within each row remains unchanged. You are given $$$B$$$ and must recover the original permutation $$$p$$$ from the first run.
Your program must recover $$$p$$$ for every possible ordering of the rows. No process state is preserved between the two runs; the shuffled matrix is the only information passed from the first run to the second. The time and memory limits apply to each run separately.
The first line contains a string op (either first or second) and an integer $$$n$$$ ($$$3\le n\le 2000$$$), indicating the run and the size of the permutation. The value of $$$n$$$ is the same in both runs.
If op is first, the second line contains $$$n$$$ integers $$$p_1,p_2,\ldots,p_n$$$ ($$$1\le p_i\le n$$$), a permutation of $$$1,2,\ldots,n$$$.
If op is second, each of the next $$$n$$$ lines contains $$$n$$$ integers, describing one row of $$$B$$$. This is the matrix output in the first run with only its rows randomly reordered.
There is one test case per run.
If op is first, output $$$n$$$ lines, each containing $$$n$$$ space-separated integers, describing the matrix $$$A$$$. Each row must contain every integer from $$$1$$$ to $$$n$$$ exactly once, and the $$$n$$$ rows must be pairwise distinct.
If op is second, output $$$n$$$ space-separated integers on one line: the original permutation $$$p$$$ from the first run, in its original order.
first 3 2 3 1
2 3 1 1 2 3 3 2 1
second 3 3 2 1 2 3 1 1 2 3
2 3 1
The two examples show the first and second runs of one possible solution on the same test.
In the first run, the input permutation is $$$(2,3,1)$$$, and the program outputs a $$$3\times 3$$$ matrix whose rows are pairwise distinct permutations of $$$1,2,3$$$.
Before the second run, the judge places the third, first, and second rows of this matrix in that order. The elements within each row remain unchanged. From the resulting matrix, the program must recover and output $$$(2,3,1)$$$. The row order used during judging may differ from the example.
Given an integer $$$n$$$, find three integers $$$a, b, c$$$ satisfying
- $$$|a|,|b|,|c|\le 10^{18};$$$
- $$$n=ab(a+b)+bc(b+c)+ac(a+c).$$$
If no such triple of integers exists, report that there is no solution.
The input contains one integer $$$n$$$ ($$$0\le n\le 10^{18}$$$).
If there is no solution, output $$$-1$$$. Otherwise, output three integers $$$a, b, c$$$ that satisfy all the requirements.
If there are multiple valid answers, output any one of them.
3
-1
6
1 1 1
You need to schedule $$$n$$$ jobs on a pipeline. The jobs form a sequence, and job $$$i$$$ has workload $$$a_i$$$. The pipeline consists of $$$m$$$ stages in series.
Before processing begins, you may choose an integer $$$t$$$ ($$$0\le t\le n$$$). This moves the first $$$t$$$ jobs to the end without changing their relative order, obtaining $$$a_{t+1},a_{t+2},\ldots,a_n,a_1,a_2,\ldots,a_t.$$$ Choosing $$$t=0$$$ or $$$t=n$$$ leaves the sequence unchanged.
Next, you need to partition the resulting sequence into at most $$$k$$$ nonempty contiguous segments, each forming a batch. The workload of a batch is the sum of the workloads of its jobs.
The batches then enter the pipeline in order. Each batch passes through stages $$$1,2,\ldots,m$$$ in this order, taking time equal to its workload at each stage. Each stage processes at most one batch at a time, following the batches' left-to-right order in the sequence. After finishing at one stage, a batch may wait for the next stage to become available. While it waits, it no longer occupies the previous stage, which may process the next batch. Different stages may process different batches simultaneously.
The pipeline starts processing at time $$$0$$$. Choose the prefix to move and the partition into batches so that all jobs finish as early as possible.
The first line contains three integers $$$n,m,k$$$ ($$$1\le n,m\le 5\times 10^5$$$, $$$1\le k\le n$$$): the number of jobs, the number of stages, and the maximum number of batches.
The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le 10^6$$$), the workloads of the jobs.
Print one integer: the minimum possible time at which all jobs have finished.
4 3 23 1 4 2
20
An optimal choice is to move the prefix $$$[3,1,4]$$$ to the end, obtaining the sequence $$$[2,3,1,4]$$$, and partition it into two batches $$$[2,3]$$$ and $$$[1,4]$$$. Both batches have workload $$$5$$$. They can start at the first stage at times $$$0$$$ and $$$5$$$, and finish at the third stage at times $$$15$$$ and $$$20$$$, respectively. Thus, all jobs finish at time $$$20$$$, which is the minimum possible time.
You enjoy exploring the world by car. Today, you have arrived in a new country consisting of $$$n$$$ cities, numbered $$$1$$$ to $$$n$$$.
You wish to drive to the capital city, $$$t$$$. Unfortunately, the country's communication network is outdated, so your navigation system does not always have a signal. However, the road network forms a weighted directed acyclic graph where the weight of each edge represents the time required to traverse it, and every city has a path to the capital city $$$t$$$ via the road network.
Upon arriving at any city other than $$$t$$$, you choose the next road according to the following rules:
- If there is a signal, the navigation system randomly selects one of the shortest paths from the current city to $$$t$$$ with equal probability, and directs you to take the first edge of that path;
- If there is no signal, you randomly select one of the city's outgoing edges with equal probability.
Consequently, in cities with a signal, the probability of selecting a specific outgoing edge is proportional to the number of shortest paths that begin with that edge; the probabilities of selecting different outgoing edges are not necessarily equal. A new choice is made after traversing each edge to reach the next city. All random choices are independent, and the journey ends immediately upon reaching the capital city $$$t$$$.
You want to determine, for each starting city $$$s$$$, the expected total time required to reach the capital city $$$t$$$, modulo $$$998244353$$$.
The first line contains three integers $$$n,~m,~t$$$ ($$$1 \le t \le n \le 2 \times 10^5$$$, $$$0 \le m \le 4 \times 10^5$$$), representing the number of cities, the number of roads, and the ID of the capital city, respectively.
The second line contains a binary string of length $$$n$$$. The $$$i$$$-th character is $$$1$$$ if city $$$i$$$ has a signal, and $$$0$$$ otherwise. The state of city $$$t$$$ does not affect the solution to the problem.
The next $$$m$$$ lines each contain three integers $$$u,~v,~w$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$, $$$1 \le w \le 10^9$$$), representing a road from $$$u$$$ to $$$v$$$ with a travel time of $$$w$$$.
The graph is guaranteed to be a directed acyclic graph; there is at most one directed edge between any pair of vertices; and $$$t$$$ is the only vertex in the graph with no outgoing edges. The number of shortest paths from any vertex to $$$t$$$ is not divisible by $$$998244353$$$.
Output $$$n$$$ integers. The $$$s$$$-th integer represents the expected total travel time from city $$$s$$$ to city $$$t$$$, modulo $$$998244353$$$.
More precisely, if the expected value is expressed as an irreducible fraction $$$p/q$$$, output $$$p\cdot q^{-1}\bmod 998244353$$$, where $$$q^{-1}$$$ is the modular multiplicative inverse of $$$q$$$. It is guaranteed that this inverse exists.
5 7 5110111 2 11 3 12 5 22 4 14 5 13 5 23 4 2
166374062 2 499122179 1 0
4 5 210104 1 14 3 51 2 11 3 13 2 1
1 0 1 4
In the first example, the three shortest paths from $$$1$$$ to $$$5$$$ are $$$1\to2\to5$$$, $$$1\to2\to4\to5$$$, and $$$1\to3\to5$$$. Therefore, at city $$$1$$$, the navigation system directs you to city $$$2$$$ with probability $$$2/3$$$ and to city $$$3$$$ with probability $$$1/3$$$—not by choosing each with a probability of $$$1/2$$$.
City $$$3$$$ has no signal, so its two outgoing edges are chosen with equal probability. The expected remaining time to reach the destination from there is $$$(2+3)/2 = 5/2$$$; the expected time starting from city $$$2$$$ is $$$2$$$. Thus, the expected time starting from city $$$1$$$ is $$$\frac23(1+2)+\frac13(1+\frac52)=\frac{19}{6}$$$, which is $$$166374062$$$ after modulo $$$998244353$$$.
In the second example, the two outgoing edges from city $$$4$$$ are chosen with equal probability. The navigation system resumes operation upon reaching city $$$1$$$ or $$$3$$$.
A system contains $$$n$$$ types of programs, indexed from $$$1$$$ to $$$n$$$. Once an instance of program type $$$k$$$ starts, it generates a log entry every $$$k$$$ seconds—specifically, at times $$$k,2k,3k,\ldots$$$ relative to its start time.
At time $$$0$$$, the system executes $$$m$$$ commands simultaneously: the $$$i$$$-th command launches one instance for each program type with an index in the range $$$[l_i, r_i]$$$. Note that if the ranges of multiple commands overlap, multiple instances of the same program type may be launched, and each instance generates logs independently.
The system records all log entries generated at times $$$1,2,\ldots,n$$$. Each record contains only the index of the program type corresponding to the instance that generated the log.
Your task is to design an algorithm to compress these logs: you must assign a non-empty binary string as an identifier to all the $$$n$$$ program types, ensuring that no identifier is a prefix of another. The cost of encoding a single record is the length of the identifier assigned to the corresponding program type, and the total cost is the sum of the costs of all records. Find the minimum possible total cost.
The first line contains two integers $$$n,m$$$ ($$$1\le n\le 10^{10}$$$, $$$1\le m\le 10^5$$$), representing the number of types of programs and the number of commands.
Each of the next $$$m$$$ lines contains two integers $$$l_i,r_i$$$ ($$$1\le l_i\le r_i\le n$$$), representing a start command.
Print a single integer: the minimum total cost.
5 11 5
20
6 21 34 6
32
Assume that logs are recorded in chronological order; for logs generated at the same time, the records follow a monotonically non-decreasing order based on the index of the corresponding program types.
For the first sample, the logs are $$$[1, 1, 2, 1, 3, 1, 2, 4, 1, 5]$$$. An optimal assignment of identifiers is (program 1: "0", program 2: "100", program 3: "101", program 4: "110", program 5: "111"). The cost is $$$5 \times 1 + 2 \times 3 + 1 \times 3 + 1 \times 3 + 1 \times 3 = 20$$$.
For the second sample, the logs are $$$[1, 1, 2, 1, 3, 1, 2, 4, 1, 5, 1, 2, 3, 6]$$$. An optimal assignment of identifiers is (program 1: "0", program 2: "10", program 3: "1100", program 4: "1101", program 5: "1110", program 6: "1111"). The cost is $$$6 \times 1 + 3 \times 2 + 2 \times 4 + 1 \times 4 + 1 \times 4 + 1 \times 4 = 32$$$.
You are given an integer sequence $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$, and an integer $$$x$$$.
Define a subsequence of the sequence as follows: for any non-empty set of indices $$$\{i_1,i_2,\cdots,i_m\}\ (i_1 \lt i_2 \lt \cdots \lt i_m)$$$ chosen from $$$1,\ldots,n$$$, taking $$$a_{i_1},\ldots,a_{i_m}$$$ in their original order is a subsequence. Define its median as follows: sort the $$$m$$$ chosen values into $$$v_1\le v_2\le\cdots\le v_m$$$, then:
- if $$$m$$$ is odd, the median is the middle value $$$v_{(m+1)/2}$$$;
- if $$$m$$$ is even, the median is the average of the two middle values, $$$\dfrac{v_{m/2}+v_{m/2+1}}{2}$$$ (this average need not be an integer, but the problem only cares whether it is exactly equal to $$$x$$$).
Find the number of subsequences whose median is exactly $$$x$$$. Since this number can be very large, output it modulo $$$998244353$$$.
Note: even if two different index sets happen to pick out the exact same multiset of values (possible since the sequence may contain repeated numbers), they are still counted as two distinct subsequences. It is the index set itself, not the multiset of chosen values, that distinguishes subsequences. The empty index set is not a subsequence and is never counted.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1\le t\le 10^4$$$).
For each testcase:
- The first line contains two integers $$$n$$$ and $$$x$$$ ($$$1\le n\le 2\times 10^5,~-10^9\le x\le 10^9$$$), representing the length of the sequence $$$a$$$ and the target median value.
- The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9\le a_i\le 10^9$$$), representing the elements of the given sequence.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\times10^5$$$.
For each test case, output one line with one integer: the number of subsequences whose median is exactly $$$x$$$, modulo $$$998244353$$$.
25 31 3 5 3 22 0-1 1
14 1
To enhance the suspense and spectator appeal of the contest, the CCPC has introduced a new format featuring a "dynamic scoreboard/balloon-awarding" system. Under this format, the specific problem numbers solved by each team are not displayed immediately during the contest; instead, the scoreboard is revealed dynamically.
Introduction to the new CCPC rules According to the rules, the scoreboard status for a specific problem "unfreezes" when any one of the following three conditions is met:
- The number of teams that have solved the problem is greater than or equal to $$$\mathbf{50}$$$.
- The number of teams that have solved the problem is greater than or equal to $$$\mathbf{20\%}$$$ of the total number of participating teams (not necessarily an integer).
- The contest enters the "scoreboard freeze" period. Specifically, the time is represented by a string in the format "HH:MM" indicating the elapsed contest time; the freeze period begins at the $$$\mathbf{240}$$$-minute mark (inclusive).
Although the new format has not yet been officially finalized and is not used in the online contest, please implement this new rule for this problem to better prepare for the upcoming on-site contests.
Given a contest with $$$n$$$ participating teams, a problem solved by $$$m$$$ teams, and the current time, please determine whether the problem currently meets the criteria for unfreezing.
The first line contains an integer $$$T$$$ ($$$1 \le T \le 100$$$), representing the number of test cases.
The next $$$T$$$ lines each contain two integers $$$n,m$$$ ($$$2\leq n\leq 10^4$$$, $$$0\leq m\leq n$$$) and a string in "HH:MM" format, representing the total number of teams, the current number of teams that have solved a specific problem, and the current time, respectively. The input guarantees that the current time is between "00:00" and "05:00" (inclusive).
For each test case, output "YES" if the unfreezing condition is met, or "NO" otherwise.
5100 50 00:00100 10 03:59100 10 04:00100 20 02:0010000 0 05:00
YES NO YES YES YES