4-й этап Республиканской олимпиады по информатике 2022-2023, 1-й тур

Задача A. Колючие ежи

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

На целочисленной прямой расположено $n$ ежей, каждый еж имеет свою координату - $x_i$ и может передвигаться по прямой как он пожелает. Но к сожалению ежам нельзя далеко уходить, поэтому при передвижении их координата должна быть целым числом между $1$ и $n$. Более того у каждого ежа есть своя скорость передвижения, а именно ежу под $i$-м номером требуется $t_i$ секунд для перехода на соседнюю точку. Ежи очень колючие существа, поэтому еж не доволен когда в одной точке с ним находится другой еж. Какое минимальное время потребуется ежам, чтобы они все стали довольными.

Формат входного файла

В первой строке дано одно натуральное число $n$ ($1 <= n <= 10^5$) — количество ежей. Далее следуют $n$ строк, в $i$ строке дано два числа $x_i$ ($1 <= x_i <= n$) и $t_i$ ($0 <= t_i <= 10^9$) — местоположение $i$-го ежа и время требуемое для передвижения на соседнюю точку $i$-го ежа.

Формат выходного файла

Выведите одно число — минимальное время для того чтобы все ежи стали довольными.

Примеры:

Вход

3
2 1
2 2
2 3

Ответ

2

Вход

6
4 1
4 7
1 9
3 0
5 11
2 14

Ответ

1

Замечание

В первом примере первый еж пойдет в точку с номером $1$(на это уйдет $1$ секунда), второй пойдет в точку с номером $3$(на это уйдет $2$ секунды), а третий остается в точке с номером $2$. Во втором примере, первый еж идет в точку номер $3$(на это уйдет $1$ секунда), четвертый еж идет в точку номер $6$($0$ секунд), а остальные ежи остаются на месте. ( Altair Ashurov )

Комментарий/решение

Бинарный поиск по ответу. В чекере представляем каждого ежа как отрезок (те элементы куда он может перейти, не превысив время), после чего проверяем можно ли каждому элементу от $1$ до $n$ сопоставить отрезок, который содержит его. Для этого жадно выбираем отрезок с наименьшей правой частью, который содержит наш элемент.

показать/скрыть код

//O(nlogˆ2n)
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <iomanip>
#include <ctime>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <cassert>
#define pb push_back
#define er erase
#define in insert1
#define s(a, x, y) sort(a.begin() + x, a.begin() + y);
#define r(a, x, y) reverse(a.begin() + x, a.begin() + y);
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
#define ll long long
#define ld long double
#define forn(i, a, b) for (ll i = a; i <= b; i++)
#define form(i, a, b) for (ll i = a; i >= b; i--)
#define PI 3.14159265358979
#define INF LLONG_MAX
#define sp setprecision
#define pii pair<int, int>
#define pll pair<ll, ll>
#define gcd __gcd
#define endl '\n'
#define sz(a) (int)a.size()
#define bt(i) (1ll << (i))
#define mxu(a, b) a = max(a, b)
#define mnu(a, b) a = min(a, b)
const int zxc = 1e5+13;
const int inf = 2147483647;
const int mod = 1e9+7;
using namespace std;

int x[zxc];
ll n;
int t[zxc];

bool check(ll time){
    vector<pii> seg(zxc);
    forn(i,1,n){
        if (t[i]==0) seg[i] = {int(n),1};
        else seg[i] = {min(x[i]+time/t[i], n), max(x[i]-time/t[i], 1ll)};
    }
    s(seg,1,n+1);
    vector<vector<int>> b(zxc);
    forn(i,1,n){
        b[seg[i].S].pb(seg[i].F);
    }
    multiset<int> q;
    int c = 0;
    forn(i,1,n){
        if (q.find(int(i)-1)!=q.end()) return 0;
        forn(j,0,sz(b[i])-1){
            q.insert(b[i][j]);
        }
        if (sz(q)==0) return 0;
        q.erase(q.begin());
        c++;
    }
    if (c<n) return 0;
    return 1;
}
    
void solve(){
    cin >> n;
    forn(i,1,n){
        cin >> x[i] >> t[i];
    }
    ll l = 0;
    ll r = 1e15;
    while (l<r){
        ll mid = (l+r)/2;
        if (check(mid)) r = mid;
        else l = mid+1;
    }
    cout << l;
}
    
    
int main()
{
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    ios_base ::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    //cin >> t;
    while (t--)solve();
}