•Tutorial•vor 2 Monaten

Educational Round #2 — Editorial

The project "Average Weight of a School Student" was undertaken by Mamed and Samed.

Why they need this number remains a mystery. They asked all the students in the school to weigh themselves and recorded the results in a table. Your task is to help them calculate the average weight of the students. However, there is a condition: when calculating the average, the students with the highest and lowest weights should not be included.

It is worth noting that Mamed and Samed forgot to count the total number of students, but this will not prevent you from completing the task.

Input. The weights of the students are given across multiple lines, separated by spaces (one or more) or by the end-of-line character. The input continues until the end of the file.

Output. Print the average weight of the students, excluding the ones with the highest and lowest weights. The result should be rounded to the nearest whole number.

beginrow

Open problem

Declare the array.

int w[1000];

Read the input data. The count of input numbers is stored in the variable $n$ .

n = 0;
while (scanf("%d", &w[n]) == 1) n++;

Find the smallest element $min$ and the largest element $ma x$ in the array.

min = max = w[0];
for (i = 0; i < n; i++)
{
  if (w[i] > max) max = w[i];
  if (w[i] < min) min = w[i];
}

Compute the sum of weights $s$ and the number of students $c n t$ , excluding those with the highest and lowest weights.

s = cnt = 0;
for (i = 0; i < n; i++)
  if (w[i] != min && w[i] != max)
  {
    s = s + w[i];
    cnt++;
 }

Print the result, rounded to the nearest whole kilogram.

printf("%.0lf\n", 1.0 * s / cnt);

Algorithm implementation — min_element, max_element

Declare the array.

vector<int> w;

Read the input data.

while (scanf("%d", &x) == 1)
  w.push_back(x);

Find the smallest element $min_e l$ and the largest element $ma x_e l$ in the array.

min_el = *min_element(w.begin(), w.end());
max_el = *max_element(w.begin(), w.end());

Compute the sum of the weights $s$ and the number of students $c n t$ , excluding those with the highest and lowest weights.

s = cnt = 0;
for (int x : w)
  if (x != min_el && x != max_el) 
  {
    s += x;
    cnt++;
  }

Print the result, rounded to the nearest whole kilogram.

printf("%.0lf\n", 1.0 * s / cnt);

One of the farming chores Farmer John dislikes the most is hauling around lots of cow manure. In order to streamline this process, he comes up with a brilliant invention: the manure teleporter! Instead of hauling manure between two points in a cart behind his tractor, he can use the manure teleporter to instantly transport manure from one location to another.

Farmer John's farm is built along a single long straight road, so any location on his farm can be described simply using its position along this road (effectively a point on the number line). A teleporter is described by two numbers $x$ and $y$ , where manure brought to location $x$ can be instantly transported to location $y$ , or vice versa.

Farmer John wants to transport manure from location $a$ to location $b$ , and he has built a teleporter that might be helpful during this process (of course, he doesn't need to use the teleporter if it doesn't help). Please help him determine the minimum amount of total distance he needs to haul the manure using his tractor.

Input. One line contains four integers: $a$ and $b$ describing the start and end locations, followed by $x$ and $y$ describing the teleporter. All positions are integers in the range $0...100$ , and they are not necessarily distinct from each-other.

Output. Print a single integer giving the minimum distance Farmer John needs to haul manure in his tractor.

Examples. In this example, the best strategy is to haul the manure from position $3$ to position $2$ , teleport it to position $8$ , then haul it to position $10$ . The total distance requiring the tractor is therefore $1 + 2 = 3$ .

beginrow

Open problem

To ensure that a number not exceeding $n$ has the maximum number of divisors, it should be represented as the product of the smallest possible prime numbers.

For example, consider numbers of the form $2^{k}$ . Find the largest $k$ such that $2^{k} \leq n$ . The number of divisors of $2^{k}$ is given by $d (2^{k}) = k + 1$ .

Next, examine the number $2^{k - 1} \cdot 3$ . The number of its divisors is $d (2^{k - 1} \cdot 3) = k \cdot 2$ , which is greater than $k + 1$ .

Thus:

If $2^{k - 1} \cdot 3 \leq n$ , the desired number is $2^{k - 1} \cdot 3$ ;
Otherwise, the answer is $2^{k}$ .

Finally, consider the special case when $n = 1$ . For this value, the answer is $1$ .

Example

Let $n = 100$ . The largest power of $2$ not exceeding $100$ is $2^{6} = 64$ . The number $64$ has $d (64) = 6 + 1 = 7$ divisors.

Now, consider the number $2^{5} \cdot 3 = 96$ . The number of its divisors is:

d (96) = (5 + 1) * (1 + 1) = 6 * 2 = 12

Since $96$ does not exceed $100$ , it will be the desired number for $n = 100$ .

One day $n$ people ( $n$ is even) met on a plaza and made two round dances. Find the number of ways $n$ people can make two round dances if each round dance consists of exactly $n /2$ people. Each person should belong to exactly one of these two round dances.

Round dance is a dance circle consisting of $1$ or more people. Two round dances are indistinguishable (equal) if one can be transformed to another by choosing the first participant. For example, round dances $[1, 3, 4, 2], [4, 2, 1, 3]$ and $[2, 1, 3, 4]$ are indistinguishable.

Input. One even integer $n (2 \leq n \leq 20)$ .

Output. Print the number of ways to make two round dances. It is guaranteed that the answer fits in the $64$ -bit integer data type.

Examples. For example, for $n = 4$ the number of ways is $3$ :

one round dance — $[1, 2]$ , another — $[3, 4]$ ;
one round dance — $[2, 4]$ , another — $[3, 1]$ ;
one round dance — $[4, 1]$ , another — $[3, 2]$ .

Open problem

First, we should select $n /2$ people for the first circle dance. This can be done in $C_{n}^{n /2}$ ways. Let's count the number of ways to arrange people within one circle dance. Fix the person who will be first, after which the remaining $n /2 - 1$ people can be arranged in any order, namely $(n /2 - 1)!$ ways. The number of ways to form two circle dances is:

C_{n}^{n /2} \cdot (n /2 - 1)! \cdot (n /2 - 1)! / 2

The division by $2$ is necessary so that we do not distinguish between pairs of circle dances $(x, y)$ and $(y, x)$ . For example, for $n = 4$ , the divisions into circle dances $([1, 2], [3, 4])$ and $([3, 4], [1, 2])$ are considered the same.

Simplifying the given formula, we get the answer:

\frac{n !}{( n /2 )! \cdot ( n /2 )!} \cdot (n /2 - 1)! \cdot (n /2 - 1)! / 2 = \frac{1}{2} \cdot \frac{n !}{( n /2 ) \cdot ( n /2 )} = \frac{2 \cdot n !}{n \cdot n} = \frac{2 \cdot ( n - 1 )!}{n}

Example

For example, for $n = 4$ the number of ways is $3$ :

One round dance — $[1, 2]$ , another — $[3, 4]$ ;
One round dance — $[2, 4]$ , another — $[3, 1]$ ;
One round dance — $[4, 1]$ , another — $[3, 2]$ .

According to the formula for $n = 4$ , the answer is

\frac{2 \cdot ( 4 - 1 )!}{4} = \frac{12}{4} = 3

Let's construct all distinguishable circle dances for $n = 4$ . We place participant $1$ in the first position. In the remaining three positions, any permutation of the other three participants can be placed.

By rotating any of these arrangements in a circle, we can obtain indistinguishable circle dances. For example, the following arrangements are indistinguishable (consider the cyclic shifts of the last permutation):

[1, 4, 3, 2], [2, 1, 4, 3], [3, 2, 1, 4], [4, 3, 2, 1]

There are $4! = 24$ circle dances with $4$ participants. However, the number of distinguishable circle dances for $n = 4$ is $3! = 6$ .

You are given a matrix of size $n \times m$ with $k$ special cells. You need to reach cell $(n, m)$ starting from $(1, 1)$ . From any cell, you are allowed to move only to the right or down.

Each of the $k$ special cells has a certain power. The $i$ -th special cell has power $p_{i}$ , and if you pass through this cell, you gain this power.

Your task is to find the total power that can be collected over all possible paths from $(1, 1)$ to $(n, m)$ .

Note that:

The power of a path is the sum of the values $p_{i}$ of all special cells visited along this path.
Regular cells that are not special have power equal to zero.

Input. The first line contains an integer $t$ — the number of test cases.

The first line of each test case contains three integers $n, m (1 \leq n, m \leq 1 0^{5})$ and $k (1 \leq k \leq 1 0^{6})$ , where $n \times m$ is the size of the grid, and $k$ is the number of special cells.

Each of the next $k$ lines contains three integers $x_{i}, y_{i} (1 \leq x_{i} \leq n, 1 \leq y_{i} \leq m)$ and $p_{i} (1 \leq p_{i} \leq 1 0^{5})$ , where $(x_{i}, y_{i})$ is the position of a special cell, and $p_{i}$ is its power.

Output. For each test case, print on a separate line the total power that can be collected. Since the result may be very large, output it modulo $1 0^{9} + 7$ .

Open problem

Declare the arrays:

$f a c t$ contains the factorials of numbers modulo $MO D$ ,
$f a c t in v$ contains the inverse values of these factorials modulo $MO D$ :

f a c t [n] = n! m o d 1000000007 f a c t in v [n] = n!^{- 1} m o d 1000000007

#define MAX 800001
ll fact[MAX], factinv[MAX];

The pow function computes the power of a number modulo $p$ : $x^{n} m o d p$ .

ll pow(ll x, ll n, ll p)
{
    if (n == 0) return 1;
    if (n % 2 == 0) return pow((x * x) % p, n / 2, p);
    return (x * pow(x, n - 1, p)) % p;
}

The inverse function finds the number that is the modular inverse of $x$ with respect to a prime modulo $p$ . Since $p$ is a prime number, by Fermat's Little Theorem the following holds:

x^{p - 1} m o d p = 1 для любого 1 \leq x < p

This can be rewritten as $(x \cdot x^{p - 2}) m o d p = 1$ , from which it follows that the modular inverse of $x$ is $x^{p - 2} m o d p$ .

ll inverse(ll x, ll p)
{
  return pow(x, p - 2, p);
}

The Cnk function computes the binomial coefficient using the formula:

C_{n}^{k} = \frac{n !}{k ! ( n - k )!}

ll Cnk(int n, int k)
{
  return ((fact[n] * factinv[k]) % MOD * factinv[n - k]) % MOD;
}

The ways function calculates the number of paths on an $n \times m$ grid from cell $(0, 0)$ to cell $(n, m)$ . Since any path between these points has length $n + m$ and contains exactly $m$ horizontal steps, the number of paths is equal to $C_{n + m}^{m}$ .

ll ways(int n, int m)
{
  return Cnk(n + m, m);
}

The main part of the program. Fill the arrays of factorials $f a c t$ and inverse factorials $f a c t in v$ .

fact[0] = 1;
for (i = 1; i < MAX; i++)
  fact[i] = (fact[i - 1] * i) % MOD;

factinv[0] = 1;
for (i = 1; i < MAX; i++)
  factinv[i] = inverse(fact[i], MOD);

Process the tests sequentially.

scanf("%d", &tests);
while (tests--)
{

Read the data for the current test.

  scanf("%d %d %d", &n, &m, &k);

Store the total obtained power in the variable $res$ .

  res = 0;

Process the $k$ special cells.

  for (i = 0; i < k; i++)
  {
    scanf("%d %d %d", &x, &y, &p);
    res = (res + (ways(x - 1, y - 1) * 
                  ways(n - x, m - y)) % MOD * p) % MOD;
  }

Print the answer for the current test.

  printf("%lld\n", res);
}

In the land of Smeshariki, a new season has begun! Now all the heroes are setting out on a journey. To do this, they need to gather at a single point, and from there continue their quest to conquer the world. Losyash, who coordinates the actions of the Smeshariki, knows the coordinates of all the participants. Help him determine the minimum number of seconds required for all the Smeshariki to gather together.

Initially, each Smesharik is located at a node of the integer grid. If a Smesharik is at point $(x, y)$ , then in one second they can move to one of the points $(x, y + 1)$ , $(x + 1, y)$ , $(x - 1, y)$ , $(x, y - 1)$ , or remain at $(x, y)$ .

Input. The first line contains a single integer $n (1 \leq n \leq 200000)$ — the number of Smeshariki. The next $n$ lines specify their initial positions. Each position is given by two integers $x_{i}$ and $y_{i} (- 1 0^{18} \leq x_{i}, y_{i} \leq 1 0^{18})$ .

Output. Print the minimum number of seconds required for all the Smeshariki to gather at a single point.

Open problem

Let a Smesharik be at the point $(x, y)$ . Then in $t$ seconds, it can reach any integer point inside the diamond, as shown in the figure.

It is required to find the smallest positive integer $t$ such that the diamonds of the corresponding size for each Smesharik will all have at least one common integer point. Let us consider the third test and illustrate the diamonds for the three Smeshariks at $t = 1, 2, 3$ .

For $t = 3$ , the Smeshariks can, for example, meet at the point $(0, 3)$ or $(1, 2)$ .

Let us rotate the coordinate system by $- 45°$ relative to the origin. Under this transformation, the diamonds will turn into squares. Let us write down the rotation formulas:

z^{'} = z e^{- i \frac{π}{4}}

Or, in Cartesian coordinates:

x^{'} + i y^{'} = (x + i y) \cdot (cos (\frac{π}{4}) - i sin (\frac{π}{4}))

{x^{'} = x \frac{2}{2} + y \frac{2}{2} y^{'} = - x \frac{2}{2} + y \frac{2}{2}

Let us eliminate the irrationality by stretching the image by a factor of $2$ . To do this, we use the following transformation:

{x^{'} = x + y y^{'} = - x + y

Now let us transform our three points:

$(0, 0) \to (0, 0)$
$(0, 3) \to (3, 3)$
$(3, 3) \to (6, 0)$

Let us find the coordinates of the rectangle containing all the points $(x_{i}^{'}, y_{i}^{'})$ — the transformed initial coordinates of the Smeshariks. Denote:

$mi n_{x} = min (x_{i}^{'}); ma x_{x} = ma x (x_{i}^{'})$ ;
$mi n_{y} = min (y_{i}^{'}); ma x_{y} = ma x (y_{i}^{'})$ ;

Then the rectangle with opposite corners $(mi n_{x}, mi n_{y})$ and $(ma x_{x}, ma x_{y})$ contains all the points $(x_{i}^{'}, y_{i}^{'})$ . Moreover, it is the minimum area rectangle whose sides are parallel to the coordinate axes.

In our example, such a rectangle is $(0, 0) - (6, 3)$ .

The meeting point of the Smeshariks $(re s_{x}, re s_{y})$ will be the center of this rectangle, that is, the point with coordinates

(re s_{x}, re s_{y}) = (\frac{mi n _{x} + ma x _{x}}{2}, \frac{mi n _{y} + ma x _{y}}{2})

Now we need to find the minimum time in which all the Smeshariks can reach the point $(re s_{x}, re s_{y})$ from their positions $(x_{i}^{'}, y_{i}^{'})$ . For the rotated diamond (a square in the new coordinate system), the distance from the point $(x_{i}^{'}, y_{i}^{'})$ to $(re s_{x}, re s_{y})$ is calculated using the formula:

ma x (∣ x_{i}^{'} - re s_{x} ∣, ∣ y_{i}^{'} - re s_{y} ∣)

Thus, all the Smeshariks will be able to gather at the point $(re s_{x}, re s_{y})$ in a time equal to the maximum of these distances:

1 \leq i \leq n max (ma x (∣ x_{i}^{'} - re s_{x} ∣, ∣ y_{i}^{'} - re s_{y} ∣))

Let us define the constant infinity $I NF L$ .

typedef long long ll;
#define INFL (ll)4e18

Store the input points in the array $in p$ .

vector<pair<ll, ll>> inp;

The function calc computes the distance from the point $(x, y)$ to the farthest Smesharik. The transformed coordinates of the Smeshariks are stored in the array $in p$ .

ll calc(ll x, ll y)
{
  ll res = 0;
  for (auto p : inp)
    res = max(res, max(abs(p.first - x), abs(p.second - y)));
  return res;
}

The main part of the program. Read the input data.

cin >> n;
minx = INFL; maxx = -INFL; miny = INFL; maxy = -INFL;
for (i = 0; i < n; i++)
{

Read the initial coordinates of the Smesharik $(x, y)$ . Perform a $- 45°$ rotation of the coordinate plane and store the resulting coordinates in the array $in p$ .

  cin >> x >> y;
  nx = x + y;
  ny = -x + y;
  inp.push_back({ nx, ny });

After that, find the coordinates of the rectangle with opposite corners $(mi n_{x}, mi n_{y})$ and $(ma x_{x}, ma x_{y})$ , which contains all the points $(x_{i}^{'}, y_{i}^{'})$ — the transformed coordinates of the Smeshariks.

  minx = min(minx, nx);
  maxx = max(maxx, nx);
  miny = min(miny, ny);
  maxy = max(maxy, ny);
}

Determine the meeting point of the Smeshariks $(re s_{x}, re s_{y})$ — the center of the rectangle.

resx = (minx + maxx) / 2;
resy = (miny + maxy) / 2;

Compute and print the minimum time required for all the Smeshariks to reach the point $(re s_{x}, re s_{y})$ from their positions $(x_{i}^{'}, y_{i}^{'})$ .

ans = calc(resx, resy);
cout << ans << "\n";

Nurlashko, Nurbakyt, and Zhora are the last warriors of an ancient ninja clan fighting against the tyranny of Emperor Ren. After a crushing defeat in open battle, they decided to split their army into three camps and switch to guerrilla warfare.

However, the absurd reforms of Emperor Ren imposed strict rules: the roads between cities can only be traveled in one direction. Moreover, the directions were chosen in such a way that it is impossible, after traversing several roads, to return to the original city.

Now the clan is deciding where to place their camps. The emperor's army regularly conducts raids, checking various routes. If, during one such raid, the enemy manages to capture all three camps, the clan will be unable to regroup and will lose the war. Your task is to help choose three cities so that there is no path passing through all of them.

Input. The first line contains two integers $n, m (1 \leq n, m \leq 1 0^{6})$ — the number of cities and roads in the empire.

The following $m$ lines each contain two integers $v_{i}, u_{i} (1 \leq v_{i}, u_{i} \leq n)$ , describing a directed road from city $v_{i}$ to city $u_{i}$ .

Output. Print three integers — the indices of the cities where the clan should place their camps. If no such triple of cities exists, print $- 1$ . If there are multiple solutions, you may output any of them.

Open problem

Declare the data structures. The input graph is represented by the adjacency list $g$ , and the in-degrees of the vertices are stored in the array $I n De g ree$ .

vector<vector<int> > g;
vector<int> InDegree;
deque<int> q;

Read the input data.

scanf("%d %d", &n, &m);
g.resize(n + 1);
InDegree.resize(n + 1);
for (i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);

For each edge $(a, b)$ , increment $I n De g ree [b]$ by $1$ .

  InDegree[b]++;
}

All vertices with an in-degree of zero are added to the queue $q$ .

for (i = 1; i < InDegree.size(); i++)
  if (InDegree[i] == 0) q.push_back(i);

The three desired vertices are stored in the variables $x, y$ and $z$ .

x = y = -1;

Continue executing the algorithm as long as the queue $q$ is not empty.

while (!q.empty())
{

If the queue contains more than one vertex at the same time, this means that the solution has been found.

  if (q.size() > 1)
  {
    x = q[0];
    y = q[1];
    break;
  }

Extract the vertex $v$ from the queue — it will become the current vertex in the topological order.

  v = q.front(); q.pop_front();

Remove from the graph all edges of the form $(v, t o)$ . For each such edge, decrease the in-degree of the vertex $t o$ . If the in-degree of $t o$ becomes zero, add it to the queue.

  for (int to : g[v])
  {
    InDegree[to]--;
    if (InDegree[to] == 0) q.push_back(to);
  }
}

Kahn's algorithm is complete. If the value of $x$ is still $- 1$ , this means that no solution exists.

if (x == -1)
  printf("-1\n");
else
{

If a solution exists, choose $z$ as the smallest vertex different from $x$ and $y$ .

  z = 1;
  while (z == x || z == y) z++;
    printf("%d %d %d\n", x, y, z);
}

Fernando was hired by the University of Waterloo to finish a development project the university started some time ago. Outside the campus, the university wanted to build its representative bungalow street for important foreign visitors and collaborators.

Currently, the street is built only partially, it begins at the lake shore and continues into the forests, where it currently ends. Fernando’s task is to complete the street at its forest end by building more bungalows there. All existing bungalows stand on one side of the street and the new ones should be built on the same side. The bungalows are of various types and painted in various colors.

The whole disposition of the street looks a bit chaotic to Fernando. He is afraid that it will look even more chaotic when he adds new bungalows of his own design. To counterbalance the chaos of all bungalow shapes, he wants to add some order to the arrangement by choosing suitable colors for the new bungalows. When the project is finished, the whole sequence of bungalow colors will be symmetric, that is, the sequence of colors is the same when observed from either end of the street.

Among other questions, Fernando wonders what is the minimum number of new bungalows he needs to build and paint appropriately to complete the project while respecting his self-imposed bungalow color constraint.

Input. The first line contains one integer $n (1 \leq n \leq 4 \cdot 1 0^{5})$ , the number of existing bungalows in the street. The next line describes the sequence of colors of the existing bungalows, from the beginning of the street at the lake. The line contains one string composed of $n$ lowercase letters (" $a$ " through " $z$ "), where different letters represent different colors.

Output. Print the minimum number of bungalows which must be added to the forest end of the street and painted appropriately to satisfy Fernando's color symmetry demand.

Open problem

A minimal number of characters must be added to the given string to turn it into a palindrome.

To do this, we need to find the longest palindromic suffix of the string, then take the prefix before the start of that palindrome, reverse it, and append it to the original string.

For example, the longest palindromic suffix of the string abcxqx is $x q x$ . The prefix before it is $ab c$ . We reverse it (getting $c ba$ ) and append it to the original string.

Consider the string $rs = re v erse (s) + s$ . Compute the $z$ -function for this string.

Next, find the smallest index $i$ (such that $i \geq n$ ) for which the equality $i + z_{i} = 2 n$ holds. Among such indices, the value $z_{i}$ will be maximal. The minimum number of characters that need to be appended to the original string to form a palindrome is $n - z_{i}$ .

For the string " $ab c x q x$ " (length $n = 6$ ), the required index is $i = 9$ , since $9 + z_{9} = 9 + 3 = 12 = 2 * 6$ .

Example

Let’s consider the first example. Compute the $z$ -function for the string $re v erse (s) + s = " bba " + " abb " = " bbaabb "$ .

The smallest index $i (i \geq n)$ for which the equality $i + z_{i} = 2 n$ holds is $i = 4$ . Indeed: $4 + z_{4} = 4 + 2 = 6 = 2 * 3$ . Therefore, the answer is $n - z_{i} = 3 - 2 = 1$ . That is, it is enough to add a single character ' $a$ ' to the string " $abb$ " to obtain the palindrome " $abba$ ".

The function z constructs and returns the $z$ -function for the string $s$ .

vector<int> zfun(string s)
{
  int i, l, r, len = s.size();
  vector<int> z(len, 0);
  l = r = 0;
  for (i = 1; i < len; i++)
  {
    if (i <= r) z[i] = min(r - i + 1, z[i - l]);
    while (i + z[i] < len && s[z[i]] == s[i + z[i]]) z[i]++;
    if (i + z[i] - 1 > r)
    {
      l = i;
      r = i + z[i] - 1;
    }
  }
  return z;
}

The main part of the program. Read the input string $s$ .

cin >> n;
cin >> s;

Construct the string $rs = re v erse (s) + s$ .

rs = s;
reverse(rs.begin(), rs.end());
rs += s;

Compute the $z$ -function for the string $rs$ .

z = zfun(rs);

Find the smallest index $i (i \geq n)$ for which the equality $i + z_{i} = 2 n$ holds. Among all such indices, the value of $z_{i}$ will be the largest.

for (i = n; i < rs.size(); i++)
  if (i + z[i] == 2 * n)
  {

Print the answer.

    cout << n - z[i] << endl;
    break;
  }

Along the Almaty - Taraz highway, there are n villages, numbered from 1 to n. With the arrival of winter, m unknown traders brought knitted hats from a certain aul and began selling them in these villages. The traders follow two principles:

They do not sell in the same place for more than one day.
Each day, they increase the price of a hat.

More formally, each $i$ -th trader:

Starts selling in village $l_{i}$ with an initial price of $x_{i}$ per hat.
Moves to a neighboring village each day: if they sold in village $j$ yesterday, they sell in village $j + 1$ today.
Increases the price by $1$ each day: if the price was $x$ yesterday, today it is $x + 1$ .
Finishes selling in village $r_{i}$ (including selling in $r_{i}$ on the last day).

For each village, determine the maximum price of a single hat throughout the entire trading history.

Input. The first line contains two integers $n (1 \leq n \leq 3 \cdot 1 0^{5})$ and $m (1 \leq m \leq 3 \cdot 1 0^{5})$ — the number of villages and the number of traders, respectively.

The next $m$ lines each contain three integers: $l_{i}, r_{i} (1 \leq l_{i} \leq r_{i} \leq n)$ and $x_{i} (1 \leq x_{i} \leq 1 0^{9})$ — the starting and ending villages, as well as the initial price of a hat for the $i$ -th trader.

Output. Print $n$ integers, where the $i$ -th number represents the maximum price of a hat throughout the entire trading history in the $i$ -th village. If no trade took place in a particular village, print $0$ .

Open problem

Construct a segment tree over the range $[1; n]$ and initially set all values to zero. Suppose a trader sold hats in villages $[l_{i}; r_{i}]$ , starting with a price of $p_{i}$ . Divide the segment $[l_{i}; r_{i}]$ into fundamental segments $[l x_{1}; r y_{1}], [l x_{2}; r y_{2}], ..., [l x_{k}; r y_{k}]$ . Then, for the node corresponding to the segment $[l x_{q}; r y_{q}] (1 \leq q \leq k)$ , store the value

p_{i} + t h e s u m o f t h e l e n g t h s o f t h e se g m e n t s [l x_{t}; r y_{t}], f or a ll t < q .

For example, let $n = 5$ , and the first trade covers the cities numbered from $2$ to $5$ , starting with a price of $4$ . Then, the segment $[2; 5]$ will be split into fundamental segments: $[2; 2], [3; 3], [4; 5]$ . After processing the first operation, the segment tree will look as follows:

If the fundamental segment $[a; b]$ contains the value $p$ , it means that:

The trader sold hats in all cities from $a$ to $b$ .
In city $a$ , the hat was sold for the price $p$ , in city $a + 1$ for the price $p + 1$ , and so on, up to city $b$ , where the price was $p + b - a$ .

Consider the procedure for processing the query $[l e f t; r i g h t]$ (the segment where the trader is trading) over the range $[lp os; r p os]$ , if the initial price of the hat is $x$ .

In the left subsegment, the merchant will sell hats in $l e n = min (mi d, r i g h t) - l e f t + 1$ cities, starting at the price $x$ . In the right subsegment, the first price of the hat in the city where the merchant arrives will be $x + l e n$ . Thus, in the segment with indices $[ma x (l e f t, mi d + 1), r i g h t]$ , the trade will start at the price $x + l e n$ . However, if $l e n < 0$ (which is possible if the entire query segment lies within the right subsegment), set $l e n = 0$ .

Consider the segment $[a; b]$ , which has two subsegments: $[a; m]$ and $[m + 1; b]$ . If the trader sold a hat for price $p$ in city $a$ , then in city $m + 1$ , the price will be $p + m + 1 - a$ .

During the query processing, implement value propagation that maintains the maximum.

To print the answer, traverse the tree, propagate all values to the leaves, and then print them.

Example

Consider the execution of the two queries given in the example. Split the query segments into fundamental segments:

$[1; 3] = [1; 3]$ ;
$[2; 4] = [2; 2] + [3; 3] + [4; 4]$ .

Declare an array $S e g T ree$ to store the segment tree.

#define MAX 300010
long long SegTree[4*MAX];

The Push function propagates the value from node $v$ to its children.

void Push(int v, int lpos, int mid, int rpos)
{
  if (SegTree[v])
  {
    SegTree[2 * v] = max(SegTree[2 * v], SegTree[v]);
    SegTree[2 * v + 1] = max(SegTree[2 * v + 1], 
                             SegTree[v] + mid - lpos + 1);
    SegTree[v] = 0;
  }
}

The Update function performs the sale of hats over the segment $[l e f t; r i g h t]$ , starting with the price $x$ .

void Update(int v, int lpos, int rpos, int left, int right, 
            long long x)
{
  if (left > right) return;
  if ((lpos == left) && (rpos == right))
    SegTree[v] = max(SegTree[v], x);
  else
  {
    int mid = (lpos + rpos) / 2;
    Push(v, lpos, mid, rpos);

    int len = min(mid, right) - left + 1;
    if (len < 0) len = 0;
    Update(2 * v, lpos, mid, left, min(mid, right), x);
    Update(2 * v + 1, mid + 1, rpos, max(left, mid + 1), 
                                         right, x + len);
    }
}

The PrintResult function propagates the values from internal nodes to the leaves and prints the final state of the array.

void PrintResult(int v, int lpos, int rpos)
{
  if (lpos == rpos)
    printf("%lld ", SegTree[v]);
  else
  {
    int mid = (lpos + rpos) / 2;
    Push(v, lpos, mid, rpos);

    PrintResult(2 * v, lpos, mid);
    PrintResult(2 * v + 1, mid + 1, rpos);
  }
}

The main part of the program. Read the input data.

scanf("%d %d", &n, &m);
memset(SegTree,0,sizeof(SegTree));

Process $m$ queries.

for(i = 0; i < m; i++)
{
  scanf("%d %d %lld", &l, &r, &x);
  Update(1,1,n,l,r,x);
}

Print the result.

PrintResult(1,1,n);
printf("\n");

Kommentare

Noch nichts

Seien Sie der Erste, der die Diskussion beginnt!

Anmelden

Laden

Einen Moment, Daten werden vom Server geholt