CSES - Pizzeria Queries

Author: Dong Liu


Time Complexity: O(NlogN)\mathcal O(N\log N)

When we query the minimum cost to buy a pizza at point ii, we can split it into two cases (iji\rightarrow j)

  1. going downwards (j<ij < i): the cost would be pjj+ip_j-j+i
  2. going upwards (j>ij > i): the cost would be pj+jip_j+j-i

Since +i+i and i-i are constant, we can first calculate the best cost and then add +i+i for the downwards cost and i-i for the upwards cost.

Thus, if we keep two min segtrees (one for going downwards and one for going upwards), we can keep track of the minimum cost by setting each value in the downwards segtree to pjjp_j-j and each value in the upwards segtree to pj+jp_j+j.

To query, we can simulate going downwards or upwards from position kk. To go downwards, we must buy pizza in the range [1k][1\dots k] so we query the minimum cost in the range [1k][1\dots k]. Going upwards is similar to going downwards, but instead of buying pizza in the range [1k][1\dots k], we're buying pizza in the range [kN][k\dots N]; thus we query the range [kN][k\dots N] in the upwards segtree.

C++

#include <bits/stdc++.h>
using namespace std;
template <class T> struct SegTree {
T U = 1e9;
T F(T a, T b) { return min(a, b); }
int N;
vector<T> t;
SegTree() {}
SegTree(int N) : N(N), t(4 * N, U) {}

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!