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

Есеп A. Тікенді кірпілер

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

2 seconds

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

256 megabytes

Бүтін сандар түзуінде $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();
}