PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author:
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
There are N positions - each of which contains either a building with positive height, or a volcano.
The volcanoes spew lava at a height of P units per second. The lava moves left and right at its current height, till it is stopped by a building with strictly larger height.
For each building, find the smallest time at which it’ll be entirely covered by lava.
EXPLANATION:
Each building can be covered from either the left side or the right side, so we can compute both times and then take the minimum of them both.
Let’s deal with only the left for now.
Define L_i to be the minimum time needed for the i-th building to be covered by a volcano from the left side.
Let j \lt i be the position of the closest volcano to the left of i. This will be the one that covers building i from the left.
There are then two possibilities:
- A_i is the largest among A_{j+1}, A_{j+2}, \ldots, A_i.
Then, the lava will take \left\lceil \frac{A_i}{p} \right\rceil seconds to cover building i, since at this point it’ll also cover all buildings to the left of i given that they’re not larger than it. - A_i is not the largest among A_{j+1}, A_{j+2}, \ldots, A_i.
Let m be the index of the maximum instead. Then, note that the lava is constrained by A_m: it cannot reach i till it entirely covers the m-th building; but once it does cover it, it will instantly cover building i since everything else is smaller.
So, in this case we have L_i = \left\lceil \frac{A_m}{p} \right\rceil instead.
Note that both cases can really be combined into a single one: the first case is just the second one but where we have m = i instead.
This gives us a pretty simple criterion for computing L_i: if j \lt i is the nearest volcano to i, and m is the index of the maximum in the range [j+1, i], we have L_i = \left\lceil \frac{A_m}{p} \right\rceil.
For completeness, we define L_i = \infty when there’s no volcano to the left of i.
To actually compute this value, note that it’s enough to just iterate i from left to right and store the index of the maximum so far.
Updating the index is easy; and whenever you encounter a volcano, reset the index instead.
This gives us all the L_i values.
Similarly, the time taken to cover each building from the right, denoted R_i, can be computed by iterating in reverse order instead.
Then the answer for each index is simply \min(L_i, R_i).
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e12;
const int MOD = 1e9 + 7;
// Function to calculate modular inverse of a number a under modulo m
int mod_inverse(int a, int m) {
int result = 1;
int power = m - 2; // Fermat's little theorem
while (power > 0) {
if (power % 2 == 1) {
result = (result * a) % m;
}
a = (a * a) % m;
power /= 2;
}
return result;
}
// Function to calculate (n / m) % MOD
int mod_divide(int n, int m) {
int inv_m = mod_inverse(m, MOD);
return (n * inv_m) % MOD;
}
int32_t main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int t,ok; cin >> t;
while (t--){
int n,p;
cin >> n >> p;
vector<int> a(n);
for(int i=0; i<n; i++) cin >> a[i];
vector<int> l(n), r(n);
int h = INF;
for(int i=0; i<n; i++){
if (a[i]==0){
h = 0;
l[i] = 0;
}
if (a[i] < h){
l[i] = h;
}
else{
l[i] = a[i];
h = a[i];
}
}
for(int i=n-1; i>=0; i--){
if (a[i]==0){
h = 0;
r[i] = 0;
}
if (a[i] < h){
r[i] = h;
}
else{
r[i] = a[i];
h = a[i];
}
}
for(int i=0; i<n; i++){
ok = min(l[i], r[i]);
cout << (ok+p-1)/p << " ";
}
cout << "\n";
}
}
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
void solve(int test_case){
ll n,k; cin >> n >> k;
vector<ll> a(n+5);
rep1(i,n) cin >> a[i];
rep1(i,n) a[i] = ceil2(a[i],k);
vector<ll> pmx(n+5), smx(n+5);
pmx[0] = smx[n+1] = inf2;
rep1(i,n){
if(a[i]){
pmx[i] = max(pmx[i-1],a[i]);
}
}
rev(i,n,1){
if(a[i]){
smx[i] = max(smx[i+1],a[i]);
}
}
rep1(i,n){
ll ans = min(pmx[i],smx[i]);
cout << ans << " ";
}
cout << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
Editorialist's code (PyPy3)
def calc(a, p):
n = len(a)
res = [0]*n
mx = (10**9 + 1) * p
for i in range(n):
if a[i] == 0: mx = 0
mx = max(mx, a[i])
res[i] = (mx + p - 1) // p
return res
for _ in range(int(input())):
n, p = map(int, input().split())
a = list(map(int, input().split()))
l = calc(a, p)
r = calc(a[::-1], p)[::-1]
ans = [min(l[i], r[i]) for i in range(n)]
print(*ans)