Добрий господар#12266
Увійти

Добрий господар (Розбір)

Автор проблеми:

De3b0o

Підготовлено:

De3b0o

Редаговано:

Hasan Saleh (MathModel)

Рішення

Значення \frac{|h_i - x|}{c} строго менше , оскільки (1 \le h_i,x \le c), тому оптимальні двері завжди матимуть мінімальне значення a_i. Якщо є кілька дверей з мінімальним значенням a_i, тоді ми вибираємо ті, що мають найближче h_i до , оскільки це дає найменшу частку.

Ми можемо відстежувати мінімальне значення a_i та обробляти оновлення і відповідати на запити за .

Складність \mathcal{O}((n+q) \cdot \log(n)).


#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
 
using namespace std;

const ll N = 2e5+9;

ll n , c , q , mn=1e9;
ll a[N],h[N];
set<pll> s[N];
multiset<ll> se;

void upd(ll id , ll b , ll d)
{
    s[a[id]].erase({h[id],id});
    se.erase(se.find(a[id]));
    a[id]=b;
    h[id]=d;
    s[a[id]].in({h[id],id});
    se.in(a[id]);
    mn=*se.begin();
}

int main()
{
    d3
    cin >> n >> c;
    for(int i = 1 ; n>=i ; i++)
        cin >> a[i],se.in(a[i]),mn=min(mn,a[i]);
    for(int i = 1 ; n>=i ; i++)
        cin >> h[i],s[a[i]].in({h[i],i});
    cin >> q;
    while(q--)
    {
        ll t;
        cin >> t;
        if(t==1)
        {
            ll x;
            cin >> x;
            ll ans=1e10;
            ll idx;
            auto it = s[mn].lower_bound({x,-1});
            if(it!=s[mn].end())
            {
                ans=abs(it->F-x);
                idx=it->S;
            }
            if(it!=s[mn].begin())
            {
                it--;
                if(abs(it->F-x)<ans)
                    idx=it->S;
            }
            cout << idx << "\n";
        }
        else
        {
            ll id , b , d;
            cin >> id >> b >> d;
            upd(id,b,d);
        }
    }
}