Blog entries - Codeforces

#	User	Rating
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

#	User	Contrib.
1	maomao90	174
2	adamant	164
2	awoo	164
4	TheScrasse	160
5	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

1802A - Likes

Idea: Aleks5d, Preparation: vaaven

Solution

Code

#include "bits/stdc++.h"

using namespace std;

void solve() {
    int n;
    cin >> n;
    int likes = 0, dislikes = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x > 0) likes++;
        else dislikes++;
    }
    for (int i = 1; i <= n; ++i) {
        if (i <= likes) cout << i << ' ';
        else cout << likes * 2 - i << ' ';
    }
    cout << '\n';

    for (int i = 1; i <= n; ++i) {
        if (i <= dislikes * 2) cout << i % 2 << ' ';
        else cout << (i - dislikes * 2) << ' ';
    }
    cout << '\n';
}

signed main() {
    int t = 1;
    cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve();
    }
    return 0;
}

1802B - Settlement of Guinea Pigs

Idea and preparation: Aleks5d

Solution

Code

#include<bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    int known = 0, unknown = 0;
    int need = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if (x == 1) ++unknown;
        else {
            known += unknown;
            unknown = 0;
        }
        need = max(need, unknown + (known ? known / 2 + 1 : 0));
    }
    cout << need << endl;
}

signed main() {
    int t = 1;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
    return 0;
}

1801A - The Very Beautiful Blanket

Idea and preparation: 4qqqq

Solution

The maximum number of different numbers we can type is always $$$n\cdot m$$$. Let's show how you can build an example for any $$$n$$$ and $$$m$$$.

Note that if we were able to construct a correct matrix, then any of its submatrix is also a correct matrix of a smaller size. Therefore, let's build a correct matrix for some $$$N$$$ and $$$M$$$, and as an answer we will output the upper left corner of this matrix of the desired size.

Take $$$N = M = 2^8$$$ and construct the matrix using the following algorithm. Let's break it into blocks of size $$$2 \times 2$$$. Let's number the blocks from left to right and from top to bottom in order, starting from zero. The $i$th block will have the form

$$$4i + 0$$$ $$$4i + 1$$$

$$$4i + 2$$$ $$$4i + 3$$$

With this construction, the bitwise exclusive OR any submatrix of size $$$2\times 2$$$ will be zero. You can verify this as follows. Let's look at the upper left corner of $$$(i,\,j)$$$ of an arbitrary submatrix of size $$$2\times 2$$$. There are 4 cases:

both coordinates are even;
$$$i$$$ is even, $$$j$$$ is odd;
$$$i$$$ odd, $$$j$$$ even;
both coordinates are odd.

Immediately note that $$$i, \, j < 200 < 2^8$$$

Consider the most unpleasant case — the last one. The remaining cases are treated in a similar way. In this case, the submatrix will have the form:

$$$4i + 3$$$ $$$4(i + 1) + 2$$$

$$$4(i + 2^8) + 1$$$ $$$4(i + 2^8 + 1) + 0$$$

Note that the second part of each term is less than 4, and the first part of each term is greater than or equal to 4. Therefore, they can be considered independently.

$$$3 \oplus 2 \oplus 1 \oplus 0$$$ $$$=$$$ $$$0$$$.

If $$$i$$$$$$=$$$$$$1$$$, then

$$$4i \oplus 4(i + 1)$$$ $$$=$$$ $$$12$$$,

$$$4(1 + 2^8) \oplus 4(2 + 2^8)$$$ $$$=$$$ $$$12$$$.

If $$$i\neq 1$$$, then

$$$4i \oplus 4(i + 1)$$$ $$$=$$$ $$$4$$$

$$$4(i + 2^8) \oplus 4(i + 2^8 + 1)$$$$$$=$$$$$$4$$$ (for $$$i=0$$$, you can check with your hands, for $$$1 < i <2^8$$$ $$$4(i+ 2^8)$$$ will be reduced and $$$4$$$ will remain from the second term).

$$$4 \oplus 4 \oplus 0$$$ $$$=$$$ $$$0$$$. Thus, in the selected submatrix, the bitwise exclusive OR is zero.

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int SZ = 256;

int v[SZ][SZ];

void Solve(){
    int n, m;
    cin >> n >> m;

    cout << n * m << '\n';

    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cout << v[i][j] << " \n"[j + 1 == m];
}

signed main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);

    {
        int now = 0;
        int n = 256;
        int m = 256;

        for(int i = 0; i < n; i += 2)
            for(int j = 0; j < m; j += 2){
                v[i][j] = now;
                v[i][j + 1] = now + 1;
                v[i + 1][j] = now + 2;
                v[i + 1][j + 1] = now + 3;
                now += 4;
            }
    }

    int num_test = 1;
    cin >> num_test;

    for(int i = 1; i <= num_test; i++){
        Solve();
    }
}

1801B - Buying gifts

Idea: Tikhon228, Preparation: DishonoredRighteous

Solution

To begin with, let's sort all departments in descending order $$$b_i$$$ (and if ~--- is equal, in ascending order $$$a_i$$$). Now let's go through the $$$i$$$ department, in which the most expensive gift for the second girlfriend will be bought. Note that in all departments with numbers $$$j < i$$$, Sasha must buy a gift for the first girlfriend, otherwise the gift $$$i$$$ will not have the maximum value among the gifts bought for the second girlfriend. Therefore, we will immediately find the value of $$$m = \max \limits_{j < i} a_j$$$. Thus, we can already get the answer $$$\lvert m - b_i\rvert$$$.

In all departments with numbers $$$j > i$$$, for which $$$a_j \le m$$$, Sasha can buy a gift for any of her friends, and this will not affect the answer in any way. Now consider all departments with numbers $$$j > i$$$ for which $$$a_j > m$$$. If you buy a gift for your first girlfriend in some of these departments, the value of $$$m$$$ will increase, which means the answer may improve. Therefore, let's iterate through all these departments and update the response with the value $$$\lvert a_j - b_i\rvert$$$.

Time $$$O(n^2)$$$.

Let's optimize this solution. To begin with, instead of calculating the value of $$$m$$$ anew at each iteration, we will maintain its value in some variable. Then, when moving from department $$$i - 1$$$ to department $$$i$$$, we will update the value of $$$m$$$ as follows: $$$m:= \max(m, a_i)$$$.

It remains to learn how to quickly find the optimal department number $$$j$$$, such that $$$j > i$$$, $$$a_j > m$$$, as well as $$$\lvert a_j - b_i\rvert$$$ is minimal. Let's choose on the suffix of the array the minimum $$$a_j$$$, such that $$$a_j\ge b_i$$$, and also the maximum $$$a_j$$$, such that $$$a_j \le b_i$$$. You can notice that the optimal $$$a_j$$$ is one of the two selected numbers (you also need to remember to check the condition $$$a_j > m$$$). Therefore, it is enough to update the answer only with the help of them.

You can search for these two elements using the \texttt{set} data structure. We will support in the set all $$$a_j$$$ located on the suffix. Then you can find the necessary two elements for $$$O(\log n)$$$. When moving from department $$$i - 1$$$ to department $$$i$$$, you need to remove the value $$$a_{i - 1}$$$ from the data structure.

Time $$$O(n\log n)$$$

Code

#include <bits/stdc++.h>

using namespace std;

template<typename T>
bool smin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool smax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const int INF = 0x3f3f3f3f;
const int N = 500100;

std::pair<int, int> a[N];

void run() {
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &a[i].first, &a[i].second);
    }

    sort(a, a + n, [&](const pair<int, int>& p1, 
                            const pair<int, int>& p2) {
        return p1.second > p2.second || (p1.second == p2.second && p1.first < p2.first);
    });

    multiset<int> setik;
    for (int i = 0; i < n; ++i) {
        setik.insert(a[i].first);
    }

    int mx = -INF;
    int ans = INF;
    
    for (int i = 1; i < n; ++i) {
        smin(ans, abs(a[i].first - a[0].second));
    }
    
    for (int i = 0; i < n; ++i) {
        setik.erase(setik.find(a[i].first));
        if (i == 0) {
            mx = a[i].first;
            continue;
        }

        smin(ans, abs(mx - a[i].second));
        auto it = setik.lower_bound(a[i].second);
        if (it != setik.end() && *it >= mx) {
            smin(ans, abs(*it - a[i].second));
        }
        if (it != setik.begin() && *std::prev(it) >= mx) {
            smin(ans, abs(*prev(it) - a[i].second));
        }

        smax(mx, a[i].first);
    }

    printf("%d\n", ans);
}

int main(void) {
    int t;
    scanf("%d", &t);
    while (t--) {
        run();
    }
    return 0;
}

1801C - Music Festival

Idea: vaaven, Preparation: ViktorSM

Solution

Let's introduce the concept of a compressed album for an album, which is obtained from the original one by removing all elements except those that are the first maxima on their corresponding prefixes.

For example:

For the album $$$[\textbf{1}, \textbf{4}, 4, 3, \textbf{6}, 5, 6]$$$ the album will be compressed $$$[1, 4, 6]$$$.

Now we note that the solution of the original problem is reduced to solving the same problem, but on compressed albums. Indeed, the answer to them will not be different, because if some element increased the impression on ordinary albums, then it will increase if you compress albums and vice versa. Next, it will be assumed that all albums have been compressed beforehand.

Let's introduce $$$dp_c$$$ — the maximum impression that can be obtained if there were no albums such that they have elements larger than $$$c$$$. Then, $$$dp_c$$$ is equal to $$$dp_{c-1}$$$, or you can add another element or two if $$$c$$$ is the maximum element for some album. Then for all compressed albums, it can be recalculated through the value of $$$dp$$$ at the point before the first element of the album, or through $$$c - 1$$$. Thus, for recalculation, it is enough to know for each $$$c$$$ which albums ended in this index, as well as for each album its first element. Solution for $$$O(K)$$$

Let's now solve the complete problem. For each value of $$$c$$$, let's remember the indexes of albums that contain an element equal to $$$c$$$. We go in order of increasing $$$c$$$, we maintain for each album the value of $$$dp_i$$$ — the maximum impression that can be obtained if there were no elements of large $$$c$$$ and Masha listened to the last $$$i$$$ album. Suppose for the next $$$c$$$ there is an album $$$i$$$, that there is a song with the coolness of $$$c$$$ in it. Then $$$dp_i$$$ should be taken as the maximum of $$$dp_i + 1$$$ and the values for all $$$dp_j + 1$$$, such that the maximum element in the $$$j$$$th album is less than the maximum element of $$$i$$$th, since she could listen to this track, either next in this album, or after listening to some other album completely. Note that you can store the value of $$$mx$$$ — maximum for all albums for which the maximum value in them is less than $$$c$$$ and recalculate it when moving to $$$c + 1$$$, storing those albums that have ended, then you will get a solution for $$$O(K + C)$$$.

Code

#include "bits/stdc++.h"
#include <algorithm>
#include <locale>
#include <random>
#include <unordered_map>
#include <vector>

using namespace std;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
typedef long long ll;
typedef long double db;
typedef unsigned long long ull;

vector<int> shrink(vector<int> &a) {
  vector<int> a1;
  int n = a.size();
  int mx = 0;
  for (int i = 0; i < n; ++i) {
    if (a[i] > mx) {
      a1.emplace_back(a[i]);
      mx = a[i];
    }
  }
  return a1;
}

void solve() {
  int n;
  cin >> n;
  vector<vector<int>> a(n);
  int k;
  for (int i = 0; i < n; ++i) {
    int k;
    cin >> k;
    a[i].resize(k);
    for (auto &j : a[i]) {
      cin >> j;
    }
  }
  vector<vector<int>> a1(n);
  for (int i = 0; i < n; ++i) {
    a1[i] = shrink(a[i]);
  }
  map<int, vector<int>> b;
  for (int i = 0; i < n; ++i) {
    for (auto &j : a1[i]) {
      b[j].emplace_back(i);
    }
  }
  vector<int> dp(n);
  int closed = 0;
  for (auto &it : b) {
    int c = it.first;
    int newclosed = 0;
    for (auto &i : it.second) {
      if (c == a1[i].back()) {
        dp[i] = max(dp[i] + 1, closed + 1);
        newclosed = max(newclosed, dp[i]);
        continue;
      }
      if (c == a1[i].front()) {
        dp[i] = closed + 1;
        continue;
      }
      dp[i] = max(dp[i] + 1, closed + 1);
    }
    closed = max(closed, newclosed);
  }
  cout << *max_element(all(dp));
}

signed main() {
  int t = 0;
  cin >> t;
  while (t --> 0) {
      solve();
      cout << '\n';
  }
  return 0;
}

1801D - The way home

Idea: Tikhon228, Preparation: Ormlis

Solution

Code

#include "bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define ar array
#define vec vector

using namespace std;

using ll = long long;
using pi = pair<int, int>;

using vi = vector<int>;
using vpi = vector<pair<int, int>>;

const ll INF = 2e18;
const int maxN = 3e5 + 10;

struct PathParams {
    ll num_show;
    int money;
};

bool operator==(const PathParams &a, const PathParams &b) {
    return tie(a.num_show, a.money) == tie(b.num_show, b.money);
}

bool operator!=(const PathParams &a, const PathParams &b) {
    return !(a == b);
}

struct State {
    PathParams params;
    int v;
    int best;
};

bool operator<(const PathParams &a, const PathParams &b) {
    if (a.num_show != b.num_show) return a.num_show < b.num_show;
    return a.money > b.money;
}

bool operator<(const State &a, const State &b) {
    return tie(a.params, a.v, a.best) < tie(b.params, b.v, b.best);
}

bool operator>(const State &a, const State &b) {
    return !(a < b);
}

void solve() {
    int n, m, p, group;
    cin >> n >> m >> p;
    vector dp(n, vector<PathParams>(n, {INF, 0}));
    vector<vpi> g(n);
    vi w(n);
    rep(i, n) cin >> w[i];
    rep(i, m) {
        int a, b, s;
        cin >> a >> b >> s;
        a--;
        b--;
        g[a].emplace_back(b, s);
    }
    dp[0][0] = {0, p};
    priority_queue<State, vector<State>, greater<>> pq;
    pq.push({.params = {.num_show=0, .money=p}, .v = 0, .best=0});
    while (!pq.empty()) {
        auto current = pq.top();
        pq.pop();
        int v = current.v;
        int best = current.best;
        if (dp[v][best] != current.params) continue;
        for (auto &[u, s]: g[v]) {
            auto state2 = current;
            PathParams &path = state2.params;
            if (path.money < s) {
                ll need = (s - path.money + w[best] - 1) / w[best];
                path.num_show += need;
                path.money += need * w[best];
                assert(path.money < s + w[best]);
            }
            path.money -= s;
            state2.v = u;
            if (w[u] > w[state2.best]) state2.best = u;
            if (path < dp[u][state2.best]) {
                dp[u][state2.best] = path;
                pq.push(state2);
            }
        }
    }
    ll ans = INF;
    rep(i, n) {
        ans = min(ans, dp[n - 1][i].num_show);
    }
    cout << (ans == INF ? -1 : ans) << '\n';
}

signed main() {
    int t = 1;
    cin >> t;
    rep(_, t) {
        solve();
    }
    return 0;
}

1801E - Gasoline prices

Idea and preparation: Kirill22

Solution

To begin with, let's understand what is required of us. A tree is given, in each vertex of which the price range for this vertex is recorded. A query is a pair of paths of equal length, the prices at the $$$i$$$-th vertices along these paths should be equal for all $$$i$$$. We need to find the number of ways to place prices at the vertices for each prefix of restrictions

Let's start with a slow solution of the problem. We will store the connectivity components (in each vertex prices should be equal). For each of them, we store an acceptable price range. The answer will be the product of the lengths of the ranges over all components. We will go along the paths and combine 2 vertices into one component using DSU. It is clear that to speed up this solution, it is necessary to search faster for the moments when two vertices are combined into one component.

First, let's analyze the long solution. Let's make a heavy-light decomposition, with which we will hash the paths in the tree, taking the root number of its components as a symbol for the vertex. Now, with the help of bin search, we will look for the first moment when the hashes on the path prefixes differ, that is, two vertices are combined into one component. With the help of transfusions, we will update the roots of their components for vertices and the tree of segments for hld. We will get $$$n$$$ unions, we will find each one for $$$O(log^2(n))$$$ using hld. There will also be $$$O(n\cdot log(n))$$$ updates in the segment tree due to overflows. For each request there will be $$$O(log^2(n))$$$ from hld. The final asymptotic $$$O((n+q)\cdot log^2(n))$$$

Now let's give a beautiful solution to this problem. Let's start with bamboo.

Replace the equality of prices on a pair of paths with two pairs of paths with lengths equal to the maximum power of two, less than the length of the original path (as in sparse table). Now the path lengths of all constraints have become powers of two. We will iterate over the powers of two in descending order $$$2^k$$$, for each path of length $$$2^k$$$ we will get a vertex in the graph, we will also get a vertex for each such path in reverse order. Now the constraints define edges in such a graph. Let's spend them, select the spanning tree. For each edge from the backbone, we divide the constraints into 2 constraints with path lengths half as long and continue the process. On a layer with lengths 1, we will get the spanning tree we need, which will be responsible for the first moments when some pairs of vertices were combined into components. Note that no more than $$$2n$$$ edges will be added down from each layer, as well as no more than $$$2q$$$ edges from queries. That is, each layer will work for $$$O((n + q)\cdot\alpha(n))$$$, where $$$\alpha(n)$$$ is the average operating time in DSU, the inverse of the Ackerman function. We got the solution in $$$O((n + q) \cdot\alpha(n)\cdot log(n))$$$

For a complete solution on the tree, first we divide a pair of paths into three pairs of corresponding vertical paths (take from the 4 end vertices of these paths the pair of vertices closest to the lca on its path, then we pair this path with a vertical path (part of another path), now we get one vertical path and an arbitrary path in the tree, let's split the second path by lca and the first by the corresponding lengths). Next, we will proceed similarly to bamboo, only the place of the vertex responsible for the segment, we will get the vertex responsible for the binary ascent in the tree to a height equal to the power of two.

Code

#include "bits/stdc++.h"

using namespace std;

const int mod = (int) 1e9 + 7;

int inv(int x) {
    int res = 1, n = mod - 2;
    while (n) {
        if (n & 1) {
            res = res * 1ll * x % mod;
        }
        x = x * 1ll * x % mod;
        n /= 2;
    }
    return res;
}

const int N = (int) 2e5 + 22, K = 18;
vector<int> g[N];
pair<int, int> a[N];
int n, q, ans = 1;
int h[N], up[N][K], lg[N];
vector<array<int, 3>> graph[K]; // lower vertex1, lower vertex2, time, vertex with direction
vector<array<int, 3>> gr[N];
vector<array<int, 3>> edges;

struct dsu {
    vector<int> p, sz;

    void build(int n) {
        p.resize(n);
        sz.resize(n);
        for (int i = 0; i < n; i++) {
            p[i] = i;
            sz[i] = 1;
        }
    }

    int get(int v) {
        return (v == p[v] ? v : p[v] = get(p[v]));
    }

    bool merge(int v, int u) {
        v = get(v), u = get(u);
        if (v != u) {
            if (sz[v] > sz[u]) {
                swap(v, u);
            }
            p[v] = u;
            sz[u] += sz[v];
            return true;
        }
        return false;
    }
} G, dsu[K];

void dfs(int v, int pr, int d) {
    h[v] = d;
    up[v][0] = pr;
    for (int j = 1; j < K; j++) {
        up[v][j] = up[up[v][j - 1]][j - 1];
    }
    for (auto u : g[v]) {
        dfs(u, v, d + 1);
    }
}

int la(int v, int x) {
    for (int j = 0; j < K; j++) {
        if (x >> j & 1) {
            v = up[v][j];
        }
    }
    return v;
}

int lca(int v, int u) {
    if (h[v] > h[u]) {
        swap(v, u);
    }
    u = la(u, h[u] - h[v]);
    if (v == u) {
        return v;
    }
    for (int j = K - 1; j >= 0; j--) {
        if (up[v][j] != up[u][j]) {
            v = up[v][j], u = up[u][j];
        }
    }
    return up[v][0];
}

int id(int v) {
    return (v > 0 ? v : -v + n);
}

int sgn(int v) {
    return (v > 0 ? 1 : -1);
}

void add_edge(int j, int v, int u, int t) {
    if (dsu[j].merge(id(v), id(u))) {
        if (j > 0) {
            if (sgn(v) == sgn(u)) {
                add_edge(j - 1, v, u, t);
                add_edge(j - 1, sgn(v) * up[abs(v)][j - 1], sgn(u) * up[abs(u)][j - 1], t);
            } else {
                if (sgn(v) == -1) {
                    swap(v, u);
                }
                add_edge(j - 1, v, sgn(u) * up[abs(u)][j - 1], t);
                add_edge(j - 1, sgn(v) * up[abs(v)][j - 1], u, t);
            }
        } else {
            edges.push_back({abs(v), abs(u), t});
        }
    }
}

void add(int v, int u, int x, int y, int t, int type1, int type2) {
    if (h[v] < h[u]) {
        swap(v, u);
    }
    if (h[x] < h[y]) {
        swap(x, y);
    }
    assert(h[v] - h[u] == h[x] - h[y]);
    int g = lg[h[v] - h[u]];
    if (type1 == type2) {
        add_edge(g, type1 * v, type2 * x, t);
        add_edge(g, type1 * la(v, h[v] - h[u] - (1 << g) + 1), type2 * la(x, h[x] - h[y] - (1 << g) + 1), t);
    } else {
        add_edge(g, type1 * v, type2 * la(x, h[x] - h[y] - (1 << g) + 1), t);
        add_edge(g, type1 * la(v, h[v] - h[u] - (1 << g) + 1), type2 * x, t);
    }
}

void merge(int v, int u) {
    v = G.get(v), u = G.get(u);
    if (v != u) {
        G.merge(v, u);
        if (G.sz[v] > G.sz[u]) {
            swap(v, u);
        }
        if (a[v].first <= a[v].second) {
            ans = ans * 1ll * inv(a[v].second - a[v].first + 1) % mod;
        }
        if (a[u].first <= a[u].second) {
            ans = ans * 1ll * inv(a[u].second - a[u].first + 1) % mod;
        }
        a[u].first = max(a[u].first, a[v].first);
        a[u].second = min(a[u].second, a[v].second);
        if (a[u].first > a[u].second) {
            ans = 0;
        } else {
            ans = ans * 1ll * (a[u].second - a[u].first + 1) % mod;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for (int j = 2; j < N; j++) {
        lg[j] = lg[j / 2] + 1;
    }
    cin >> n;
    for (int i = 2; i <= n; i++) {
        int v;
        cin >> v;
        g[v].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i].first >> a[i].second;
        ans = ans * 1ll * (a[i].second - a[i].first + 1) % mod;
    }
    dfs(1, 1, 0);
    cin >> q;
    for (int j = 0; j < K; j++) {
        dsu[j].build(2 * n + 1);
    }
    for (int i = 0; i < q; i++) {
        int v, u, x, y;
        cin >> v >> u >> x >> y;
        int w = lca(v, u);
        int z = lca(x, y);
        if (h[v] - h[w] > h[x] - h[z]) {
            swap(v, x);
            swap(u, y);
            swap(w, z);
        }
        if (v != w) {
            int d = h[v] - h[w];
            int v2 = la(v, d - 1);
            int x2 = la(x, d - 1);
            add(v, v2, x, x2, i, 1, 1);
            v = up[v2][0];
            x = up[x2][0];
        }
        if (x != z) {
            int d = h[x] - h[z];
            int v2 = la(u, (h[u] - h[v]) - d);
            int x2 = la(x, d - 1);
            add(v, up[v2][0], x, x2, i, -1, 1);
            v = v2;
            x = up[x2][0];
        }
        add(v, u, x, y, i, (h[v] > h[u] ? 1 : -1), (h[x] > h[y] ? 1 : -1));
    }
    G.build(n + 1);
    int j = 0;
    for (int i = 0; i < q; i++) {
        while (j < (int) edges.size() && edges[j][2] == i) {
            merge(edges[j][0], edges[j][1]);
            j++;
        }
        cout << ans << '\n';
    }
}

1801F - Another n-dimensional chocolate bar

Idea and preparation: Tikhon228

Solution

For $$$A$$$ we denote the maximum value of $$$a_i$$$

To begin with, let's solve the problem for $$$O(n\cdot k\cdot f(k, A))$$$ using dynamic programming.

Let's put $$$dp[i][j]$$$— the maximum possible volume of the smallest piece, if by the first $$$i$$$ measurements we divided the chocolate into $$$j$$$ parts. If we have divided into more than $$$k$$$ parts, we will also put the result in $$$dp[i][k]$$$. In terms of calculation, we need to decide how many hours to divide the chocolate bar along the next dimension. Let's look at several ways to do this.

It is possible for $$$O(k)$$$ to sort out the state to which we are moving, and from this calculate how many parts you need to divide the chocolate bar along the next dimension. — We get $$$O(n\cdot k^2)$$$
It is possible for $$$O(A)$$$ to sort out how many parts we divide the chocolate bar along the next dimension.
Being in the state of $$$dp[i][j]$$$, you can iterate over $$$b_i$$$ — into how many parts to divide the chocolate until $$$j\cdot b_i\le k$$$. It can be shown that such a solution will work for $$$O(n\cdot k\cdot\ln{k})$$$

The key idea

suppose we need to divide a chocolate bar into $$$10$$$ parts, and along the first measurements we have already divided it into $$$5$$$ parts, or $$$6$$$ parts, or $$$7, 8$$$ or $$$9$$$ parts. All these states are not distinguishable for us, because in all these cases we need to divide the chocolate bar into at least $$$2$$$ parts. It remains to understand how many such <> states there are and learn how to store them. There are several approaches for this, let's analyze one of them:
we are interested in all the values of $$$\lceil\frac{k}{i}\rceil$$$ for $$$i = 1, 2, \ldots k$$$— this is how many parts the chocolate bar may still need to be divided into. Among them, only $$$O(\sqrt{k})$$$different, since either $$$i\le\sqrt{k}$$$, or the value of $$$\lceil\frac{k}{i}\rceil\le\sqrt{k}$$$ itself. If we make all these numbers states, and recalculate, iterating over the state to which to go, we get $$$O(n\cdot\sqrt{k} \cdot\sqrt{k}) = O(n\cdot k)$$$— this is still not enough to solve the hollow problem.

Last observation

If we are in the state of $$$dp[i][remain]$$$ where $$$remain = \lceil\frac{k}{i}\rceil$$$ for some $$$i$$$, we will apply the same idea to it. From it, we are interested in transitions to the states $$$\lceil \frac{remain}{j} \rceil$$$ for $$$j = 1, 2, \ldots remain$$$. What kind of asymptotics will be obtained if we iterate over only interesting transitions?

$$$n \cdot (\sum\limits_{r=1}^{\sqrt{k}}{ 2 \cdot \sqrt{r} + 2 \cdot \sqrt{\lceil \frac{k}{r} \rceil}})$$$

it can be shown that this is $$$O(n\cdot k^{3/4})$$$— which solves the problem

Code

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200;
int a[MAXN];

const int MAXK = 1e7 + 100, MAXH = 1e4;
int hsh[MAXK];
int rev[MAXH];

double dp[MAXN][MAXH];

vector<array<int, 2>> go[MAXH];

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int id = 0;
    for (int c = 1;; ++id) {
        rev[id] = (k + c - 1) / c;
        hsh[(k + c - 1) / c] = id;
        int t = (k + c - 1) / c - 1;
        if (t == 0) break;
        c = (k + t - 1) / t;
    }
    ++id;
    dp[0][hsh[k]] = k;

    for (int i = 0; i < id; ++i) {
        int k = rev[i];
        for (int c = 1;;) {
            go[i].push_back({c, hsh[(k + c - 1) / c]});
            int t = (k + c - 1) / c - 1;
            if (t == 0) break;
            c = (k + t - 1) / t;
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < id; ++j) {
            double val = dp[i][j];
            if (val == 0) continue;
            for (auto elem : go[j]) {
                int c = elem[0], k1 = elem[1];
                if (c > a[i]) break;
                int cur = a[i] / c;
                dp[i + 1][k1] = max(dp[i + 1][k1], val * cur / a[i]);
            }
        }
    }
    cout << fixed << setprecision(20);
    cout << dp[n][hsh[1]] << '\n';
    return 0;
}

1801G - A task for substrings

Idea and preparation: grphil

Solution

Code

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

struct node {
	int nx[26];
	int p;
	int pp;
	int len;
	int id;
	int cnt;
	bool term;

	node() : p(-1), pp(-1), len(0), id(-1), term(false), cnt(0) {
		for (int i = 0; i < 26; i++) {
			nx[i] = -1;
		}
	}
};

vector<node> g;

vector<string> s[2];

string t[2];

vector<vector<long long>> c[2], pid[2];

vector<long long> tc[2];

int add(int a, char c) {
	c -= 'a';
	if (g[a].nx[c] == -1) {
		g[a].nx[c] = g.size();
		g.emplace_back();
		g.back().len = g[a].len + 1;
	}
	return g[a].nx[c];
}

void build_aho(int a) {
	vector<pair<int, int>> q;
	for (int i = 0; i < 26; i++) {
		if (g[a].nx[i] == -1) {
			g[a].nx[i] = a;
		} else {
			q.emplace_back(a, i);
		}
	}

	int qb = 0;
	while (qb < q.size()) {
		int b = q[qb].x;
		int i = q[qb].y;
		qb++;
		int v = g[b].nx[i];
		int c = g[b].p;

		if (g[v].term) { // bug in c != -1
			g[v].cnt = 1;
		}

		if (c == -1) {
			g[v].p = a;
			g[b].pp = -1;
		} else {
			g[v].p = g[c].nx[i];
			if (g[v].term) {
				g[v].pp = v;
			} else {
				g[v].pp = g[g[v].p].pp;
			}
			g[v].cnt += g[g[v].p].cnt;
		}

		for (int i = 0; i < 26; i++) {
			if (g[v].nx[i] == -1) {
				g[v].nx[i] = g[g[v].p].nx[i];
			} else {
				q.emplace_back(v, i);
			}
		}
	}
}

vector<vector<pair<int, int>>> ts;
vector<int> qlen;
priority_queue<pair<int, int>> h;
vector<long long> ans;

long long get_ans(int rdst, int len, vector<long long>& a, vector<long long>& b, bool substr) {
	int l = a.size() - 1 - rdst;
	int r = l + len;
	long long cnt = a[r] + b[a.size() - 1 - l] - a.back();
	if (substr && l == 0 && r == a.size() - 1) {
		cnt++;
	}

	return cnt;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, m;
	cin >> n >> m;
	g.emplace_back(); g.emplace_back();
	s[0].resize(n); s[1].resize(n);
	c[0].resize(n); c[1].resize(n);
	pid[0].resize(n); pid[1].resize(n);
	ans.resize(m);

	cin >> t[0];
	t[1] = t[0];
	reverse(t[1].begin(), t[1].end());
	ts.resize(t[0].size());

	for (int i = 0; i < n; i++) {
		cin >> s[0][i];
	}
	sort(s[0].begin(), s[0].end(), \ 
	[](const string& a, const string& b) { return a.size() < b.size(); });

	for (int i = 0; i < n; i++) {
		s[1][i] = s[0][i];
		reverse(s[1][i].begin(), s[1][i].end());

		for (int e = 0; e < 2; e++) {
			int a = e;
			for (auto j : s[e][i]) {
				a = add(a, j);
			}
			g[a].term = true;
			g[a].id = i;
		}
	}

	build_aho(0); build_aho(1);

	for (int e = 0; e < 2; e++) {
		tc[e].resize(t[0].size() + 1);

		int a = e;
		for (int i = 0; i < t[0].size(); i++) {
			a = g[a].nx[t[e][i] - 'a'];
			tc[e][i + 1] = tc[e][i] + g[a].cnt;
		}
		for (int i = 0; i < n; i++) {;
			c[e][i].resize(s[0][i].size() + 1);
			pid[e][i].resize(s[0][i].size() + 1, -1);

			int a = e;
			for (int j = 0; j < s[e][i].size(); j++) {
				a = g[a].nx[s[e][i][j] - 'a'];
				c[e][i][j + 1] = c[e][i][j] + g[a].cnt;
				
				if (g[a].term) { // bug always
					pid[e][i][j + 1] = g[a].id;
				}
			}

			for (int j = (int)s[e][i].size() - 1; j >= 0; j--) { // bug forget
				if (pid[e][i][j] == -1) {
					pid[e][i][j] = pid[e][i][j + 1];
				}
			}
			c[e][i].back()--; // bug forget string itself
			
		}
	}

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		ts[b - 1].emplace_back(a, i);
		qlen.emplace_back(b - a);
	}

	int a = 0;
	for (int i = 0; i < t[0].size(); i++) {
		// cout << i << ' ' << t[0][i] << '\n';
		for (auto j : ts[i]) {
			h.emplace(j);
		}

		a = g[a].nx[t[0][i] - 'a'];

		if (g[a].pp != -1) { // bug ignore
			int id = g[g[a].pp].id;
			int bg = i + 1 - (int)s[0][id].size();
			while (h.size() > 0 && h.top().x >= bg) {
				int rdst = i - h.top().x + 1;
				int nid = pid[1][id][rdst]; // bug forget

				// cout << h.top().x << ' ' << h.top().y << ' ' << rdst << ' ' << nid << '\n';

				ans[h.top().y] = get_ans(rdst, qlen[h.top().y], 
				    c[0][nid], c[1][nid], true);
				h.pop();
			}
		}
	}

	while (h.size() > 0) {
		// cout << h.top().x << ' ' << h.top().y << '\n';
		ans[h.top().y] = get_ans(t[0].size() - h.top().x, qlen[h.top().y], tc[0], tc[1], false);
		h.pop();
	}

	for (auto i : ans) {
		cout << i << ' ';
	}
	cout << '\n';
}

Full text and comments »

1793A - Yet Another Promotion was authored and prepared by Ormlis

1793B - Fedya and Array was authored and prepared by TheEvilBird

1793C - Dora and Search was authored by fedoseev.timofey and prepared by vaaven

1793D - Moscow Gorillas was authored and prepared by Gornak40

1793E - Velepin and Marketing was authored and prepared by Tikhon228

1793F - Rebrending was authored by Tikhon228 and prepared by vaaven

1793A - Yet Another Promotion

Let $$$n = (m + 1) \cdot q + r$$$.

Note that you need to use a promotion if $$$a \cdot m \leq b \cdot (m + 1)$$$. In this case, we will buy potatoes $$$q$$$ times for the promotion. The remaining potatoes (or all if the promotion is unprofitable) can be bought at $$$\min(a, b)$$$ per kilogram.

Then the answer is:

$$$q \cdot \min(a \cdot m, b \cdot (m + 1)) + r \cdot \min(a, b)$$$

Thus this solution works in $$$\mathcal{O}(1)$$$

Code

t = int(input())

for i in range(t):
    a, b = map(int, input().split(" "))
    n, m = map(int, input().split(" "))

    q = n // (m + 1)
    r = n - q * (m + 1)
    print(q * min(a * m, b * (m + 1))+ r*min(a,b))

1793B - Fedya and Array

Note that the local minimums and maximums will alternate, and there will be the same number of them $$$k$$$. Let's call the $$$i$$$-th local maximum by $$$a_i$$$, the $$$i$$$-th local minimum by $$$b_i$$$. Without loss of generality, consider that $$$a_i$$$ goes before $$$b_i$$$. To get $$$b_i$$$ from $$$a_i$$$ we need to write out $$$a_i - b_i$$$ numbers, to get $$$a_{(i + 1) \bmod k}$$$ from $$$b_i$$$ we need to write out $$$a_{(i + 1) \bmod k} - b_i$$$ numbers.

Thus, $$$(a_1 - b_1) + (a_2 - b_1) + (a_2 - b_2) + \ldots + (a_k - b_k) + (a_1 - b_k) =$$$

$$$= 2 \cdot (a_1 + a_2 + \ldots + a_k) - 2 \cdot (b_1 + b_2 + \ldots + b_k) = 2 \cdot (A - B) = n$$$

The array $$$[y, y + 1, y + 2, \ldots, x - 1, x, x - 1, x - 2, \ldots, y + 1]$$$ will satisfy the condition.

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void solve() {
    ll a, b;
    cin >> a >> b;
    ll n = 2 * (a - b);
    cout << n << '\n';
    vector<ll> arr(n);
    int ptr = 0;
    for (ll c = b; c <= a; ++c) {
        arr[ptr++] = c;
    }
    for (ll c = a - 1; c > b; --c) {
        arr[ptr++] = c;
    }
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " \n"[i == n - 1];
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

1793C - Dora and Search

Suppose we want to check whether the entire array satisfies the claim. If this is the case, then we can output the entire array as an answer. Otherwise, one of the two extreme elements does not meet our requirements. From this we can conclude that all segments containing an element that does not meet our requirements will also be incorrect, because this extreme element will remain the minimum/maximum.

The algorithm follows from the fact above: let's look at the sub-section $$$[l; r]$$$, which is initially equal to $$$[1; n]$$$. If $$$a_l = \min(a_{l}, a_{l+1}, \ldots, a_{r})$$$ or $$$a_l = \max(a_l, a_{l +1}, \ldots, a_r)$$$, then we proceed to the segment $$$[l+1; r]$$$. A similar reasoning is also needed for $$$a_r$$$. Thus, either after some iterations we will get the required sub-section, or we will get $$$l == r$$$ and the answer will be $$$-1$$$.

Final asymptotics: $$$\mathcal{O}(n\log n)$$$ or $$$\mathcal{O}(n)$$$ depending on the implementation.

Code

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;

void solve() {
    int n;
    cin >> n;
    vi a(n);
    for (int &i: a)
        cin >> i;
    int l = 0, r = n - 1;
    int mn = 1, mx = n;
    while (l <= r) {
        if (a[l] == mn) {
            l++;
            mn++;
        } else if (a[l] == mx) {
            l++;
            mx--;
        } else if (a[r] == mn) {
            r--;
            mn++;
        } else if (a[r] == mx) {
            r--;
            mx--;
        } else {
            break;
        }
    }
    if(l <= r){
        cout << l + 1 << " " << r + 1 << endl;
    } else{
        cout << -1 << endl;
    }
}

signed main() {
    int q = 1;
    cin >> q;
    while (q--)
        solve();
    return 0;
}

1793D - Moscow Gorillas

Denote by $$$pos_x$$$ the index of the number $$$x$$$ in the permutation. Subsegments with $$$\operatorname{MEX}>1$$$ are as follows $$$1 \le l \le pos_1 \le r \le n$$$.

Denote by: $$$l_x = \min{[pos_1, pos_2, \ldots, pos_x]}$$$, $$$r_x=\max{[pos_1, pos_2, \ldots, os_x]}$$$.

Subsegments with $$$\operatorname{MEX}>x$$$ are as follows $$$1 \le l \le l_x \le r_x \le r \le n$$$. Let's find all subsegments with $$$\operatorname{MEX}=x$$$.

If $$$pos_{x + 1} < l_x$$$, then the subsegments with $$$\operatorname{MEX}=x+1$$$ are as follows $$$pos_{x+1} < l \le l_x \le r_x \le r \le n$$$

If $$$l_x \le pos_{x + 1} \le r_x$$$, then there is no subsegment with $$$\operatorname{MEX}=x+1$$$

If $$$r_x <pos_{x+1}$$$, then the subsegments with $$$\operatorname{MEX}=x+1$$$ are as follows $$$1 \le l \le l_x \le r_x \le r < pos_{x+1}$$$

It remains only to intersect the sets of such subsegments for $$$p$$$ and $$$q$$$, which is done trivially.

Code

#include <bits/stdc++.h>
#define int long long

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> pos_a(n + 1);
    vector<int> pos_b(n + 1);
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        pos_a[a] = i + 1;
    }
    for (int i = 0; i < n; i++) {
        int b;
        cin >> b;
        pos_b[b] = i + 1;
    }
    int la = n, ra = 1, lb = n, rb = 1, ans = 0;
    for (int i = 1; i + 1 <= n; i++) {
        la = min(la, pos_a[i]);
        ra = max(ra, pos_a[i]);
        lb = min(lb, pos_b[i]);
        rb = max(rb, pos_b[i]);
        int min_la, max_ra, min_lb, max_rb;
        if (pos_a[i + 1] < la) {
            min_la = pos_a[i + 1] + 1;
            max_ra = n;
        } else {
            min_la = 1;
            max_ra = pos_a[i + 1] - 1;
        }
        if (pos_b[i + 1] < lb) {
            min_lb = pos_b[i + 1] + 1;
            max_rb = n;
        } else {
            min_lb = 1;
            max_rb = pos_b[i + 1] - 1;
        }
        ans += max(min(la, lb) - max(min_la, min_lb) + 1, 0ll) * max(min(max_ra, max_rb) - max(ra, rb) + 1, 0ll);
    }
    ans += min(pos_a[1], pos_b[1]) * (min(pos_a[1], pos_b[1]) - 1) / 2;
    ans += (n - max(pos_a[1], pos_b[1])) * (n - max(pos_a[1], pos_b[1]) + 1) / 2;
    ans += abs(pos_a[1] - pos_b[1]) * (abs(pos_a[1] - pos_b[1]) - 1) / 2;
    ans++;
    cout << ans << endl;
}

signed main() {
    int q = 1;
    while (q--)
        solve();
    return 0;
}

1793E - Velepin and Marketing

Let's sort people by their group size requirement. Suppose we have such a person $$$i$$$ that he is not satisfied, and we have a person $$$j > i$$$ who is satisfied. Then we can replace person $$$j$$$ in his group with $$$i$$$ and the answer for us will not be worse. It follows that for a particular $$$k$$$ the answer is some prefix of the people we can make satisfied.

Let us also prove that there exists some arrangement of groups that covers the same prefix, and that each group is a continuous segment. Let's take some correct partitioning into groups. Then each group will be a set of unconnected segments. Let's take the leftmost such segment. Note that we can swap it to the nearest segment of the same group to the right without breaking anything.

Thus we obtained that we can look for a solution in the form of partitioning each prefix into valid groups, which are segments. We will solve this problem using dynamic programming.

Let $$$dp[i]$$$ -- the maximum number of groups into which $$$i$$$th prefix can be partitioned, so that everyone is satisfied (and no elements beyond the prefix can be used). Dynamics base: $$$dp[0] = 0$$$ (empty prefix maximum can be divided into 0 groups). Transition: for $$$i$$$th person his group must have size at least $$$a[i]$$$, so the transition looks like this $$$dp[i] = \underset{0 \leqslant j \leqslant i - a[i]}{\max} dp[j] + 1$$$. But what if $$$a[i] > i$$$? Then we can't dial the $$$i$$$th prefix. Then we put $$$dp[i] = -\infty$$$. This dynamics can be calculated using prefix maximums. This part of the solution works for $$$\mathcal{O}(n)$$$.

Earlier we said that the answer would be some prefix of people who would be satisfied. If we can partition the prefix into some number of groups, then that answer can be the prefix for all $$$k \leqslant dp[i] + n - i$$$. (we partition our prefix into $$$dp$$$, and the rest of the people one by one into the group)

If we can't make the whole prefix satisfied ($$$dp[i] = -\infty$$$), then we need to add people from outside. Thus, the maximum number of groups we can split into if $$$i$$$th prefix is completely satisfied is $$$n - a[i] + 1$$$.

Note that if by some prefix we can score $$$k$$$, then we can also score $$$k - 1$$$ (combining two groups into one). Then we need to find the largest prefix that fits the given $$$k$$$ in the query. This can be done by an array of suffix maximums over $$$\mathcal{O}(q)$$$ total. The final asymptotic of the solution is $$$\mathcal{O}(n \log n + q)$$$.

Code

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()

const int inf = 1e9 + 7;

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    vector<int> c(n);
    for (int i = 0; i < n; ++i) cin >> c[i];
    sort(all(c));
    vector<int> ans(n + 1); 
    vector<int> dp(n + 1, -inf);
    dp[0] = 0;

    for (int i = 1; i <= n; ++i) {
        if (c[i-1] <= i) {
            dp[i] = dp[i - c[i-1]] + 1;
            ans[dp[i] + n - i] = max(ans[dp[i] + n - i], i);
        } else {
            if (c[i-1] <= n) {
                ans[1 + n - c[i-1]] = max(ans[1 + n - c[i-1]], i);
            }
        }
        dp[i] = max(dp[i], dp[i-1]);
    }

    for (int i = n - 1; i >= 0; i--) {
        ans[i] = max(ans[i], ans[i + 1]);
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int x;
        cin >> x;
        cout << ans[x] << '\n';
    }

    return 0;
}

1793F - Rebrending

Let's go through all the elements from left to right. The main task will be to support the current version of $$$dp[i]$$$ -- the minimum difference of $$$a_i$$$ with the elements to the right of it that we managed to consider. Let us correctly calculate $$$dp$$$ for the first $$$r$$$ elements. Let's move on to $$$r + 1$$$. Let's show how to update the answer for all $$$j < i$$$, such that $$$a[j] > a[i]$$$. For $$$j < i$$$, such that $$$a[j] <a[i]$$$ is solved similarly.

Let's take the first element $$$a[j]$$$ to the left of $$$i$$$, such that $$$a[j] > a[i]$$$. Note that if there is $$$l<j < i$$$ such that $$$a[l] > a[j]> a[i]$$$, then we will not update $$$dp[l]$$$ for it, because $$$|a[l] - a[j]| < |a[l] - a[i]|$$$. Also, we will not update the answer for $$$l$$$ such that $$$|a[l] - a[j]| < |a[l] - a[i]|$$$, that is, if $$$a[l] > a[i] + \frac{a[j] - a[i]}{2}$$$. Therefore, further we will be interested only in the numbers from the segment $$$\left[a[i], a[i] + \frac{a[j] - a[i]}{2}\right]$$$.

Let's note that we have reduced the length of the segment by $$$2$$$ times. That is, there will be no more such iterations than $$$\mathcal{O}(\log n)$$$. You can find the rightmost number belonging to a segment using the segment tree. The answer for the segment $$$l_i, r_i$$$ will be $$$\underset{l_i\leqslant j<r}{\min} dp[l]$$$ at the moment $$$r_i$$$. This can also be efficiently found using the segment tree. The final asymptotics of the solution is $$$\mathcal{O}(n\log^2 n + q\log n)$$$.

There is also a solution for $$$\mathcal{O}(n\sqrt{n} + q\log q)$$$ that passes all the tests.

Code

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9 + 228;

template<class T, class Fun = function<T(const T &, const T &)>>
struct SegTree {
    Fun f;
    vector<T> t;
    int n;

    SegTree(int sz, const Fun &g, T default_value = T()) : f(g) {
        n = 1;
        while (n < sz) n <<= 1;
        t.resize(n * 2, default_value);
    }

    SegTree(vector<T> &a, const Fun &g, T default_value = T()) : SegTree(a.size(), g, default_value) {
        for (int i = 0; i < n; ++i) t[i + n] = a[i];
        for (int i = n - 1; i >= 1; --i) t[i] = f(t[i << 1], t[i << 1 | 1]);
    }

    void upd(int i, T x) {
        i += n;
        t[i] = f(t[i], x);
        for (i >>= 1; i > 1; i >>= 1) t[i] = f(t[i << 1], t[i << 1 | 1]);
    }

    T get(int l, int r) {
        T resL = t[0], resR = t[0];
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) resL = f(resL, t[l++]);
            if (r & 1) resR = f(t[--r], resR);
        }
        return f(resL, resR);
    }
};

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<vector<pair<int, int>>> posts(n);
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        posts[r].push_back({l, i});
    }
    SegTree<int> ind(n + 1, [](int x, int y) { return max(x, y); }, -1);
    SegTree<int> dp(n + 1, [](int x, int y) { return min(x, y); }, inf);
    vector<int> answer(q);
    for (int i = 0; i < n; i++) {
        {
            int limit = n + 1;
            while (true) {
                int j = ind.get(a[i], limit);
                if (j == -1)
                    break;
                dp.upd(j, abs(a[j] - a[i]));
                limit = a[i] + (a[j] - a[i] + 1) / 2;
            }
        }
        {
            int limit = 0;
            while (true) {
                int j = ind.get(limit, a[i]);
                if (j == -1)
                    break;
                dp.upd(j, abs(a[j] - a[i]));
                limit = a[i] - (a[i] - a[j] + 1) / 2 + 1;
            }
        }
        ind.upd(a[i], i);
        for (pair<int, int> j: posts[i]) {
            answer[j.second] = dp.get(j.first, i);
        }
    }
    for (int i: answer) {
        cout << i << "\n";
    }

    return 0;
}

Full text and comments »