Під парасолею#13062

Під парасолею (Розбір)

Автор задачі:	Andrii Kholod (Connect)
Підготував:	Andrii Kholod (Connect)
Розбір:	Andrii Kholod (Connect)

Розв'язання

Припустимо, що ми хочемо врятувати білку $i$ .

Якщо ліва межа парасолі знаходиться в точці $p$ , то білка $i$ захищена тоді й лише тоді, коли

$p \leq x_{i} \leq p + w .$ p \le x_i \le p+w.

Отже,

$x_{i} - w \leq p \leq x_{i} .$ x_i-w \le p \le x_i.

Водночас парасоля завжди повинна повністю знаходитися між першою та останньою білкою, тому

$x_{1} \leq p \leq x_{n} - w .$ x_1 \le p \le x_n-w.

Тому в кожен момент, коли білку $i$ потрібно захистити, ліва межа парасолі повинна належати відрізку

$I_{i} = [max (x_{1}, x_{i} - w), min (x_{n} - w, x_{i})] .$ I_i= [\max(x_1,x_i-w),\min(x_n-w,x_i)].

Тепер розглянемо двох білок $i$ та $j$ , яких потрібно захистити в моменти часу $t_{i}$ t_i та $t_{j}$ t_j.

Мінімальна відстань між їхніми допустимими відрізками дорівнює

$dist (I_{i}, I_{j}) = max (0, ∣ x_{i} - x_{j} ∣ - w) .$ \operatorname{dist}(I_i,I_j) = \max(0,|x_i-x_j|-w).

Оскільки парасоля може переміщатися не більше ніж на одну координатну одиницю за одиницю часу, ці дві вимоги сумісні тоді й лише тоді, коли

$max (0, ∣ x_{i} - x_{j} ∣ - w) \leq ∣ t_{i} - t_{j} ∣.$ \max(0,|x_i-x_j|-w)\le |t_i-t_j|.

Еквівалентно, вони несумісні, якщо

$∣ x_{i} - x_{j} ∣ > w + ∣ t_{i} - t_{j} ∣.$ |x_i-x_j|>w+|t_i-t_j|.

Важливим спостереженням є те, що достатньо перевірити сумісність кожної пари вимог.

Припустимо, що кожна пара вимог сумісна. Для кожної вимоги $k$ нехай її допустимий відрізок дорівнює $[L_{k}, R_{k}]$ [L_k,R_k], а момент часу — $t_{k}$ t_k.

Розглянемо функцію

$f (t) = max_{k} (L_{k} - ∣ t - t_{k} ∣) .$ f(t)=\max_k(L_k-|t-t_k|).

Кожна функція всередині максимуму змінюється зі швидкістю не більшою за $1$ , тому $f$ також змінюється зі швидкістю не більшою за $1$ .

Для кожної вимоги $j$ очевидно маємо

$f (t_{j}) \geq L_{j} .$ f(t_j)\ge L_j.

Із попарної сумісності для кожного $k$ також маємо

$L_{k} - R_{j} \leq ∣ t_{k} - t_{j} ∣.$ L_k-R_j\le |t_k-t_j|.

Отже,

$L_{k} - ∣ t_{j} - t_{k} ∣ \leq R_{j},$ L_k-|t_j-t_k|\le R_j,

а тому

$f (t_{j}) \leq R_{j} .$ f(t_j)\le R_j.

Таким чином,

$f (t_{j}) \in [L_{j}, R_{j}]$ f(t_j)\in[L_j,R_j]

для кожної вимоги.

За потреби можна додатково обмежити $f (t)$ відрізком $[x_{1}, x_{n} - w]$ [x_1,x_n-w]. Це не збільшить швидкість зміни функції та не завадить виконанню жодної вимоги.

Отже, всі попарно сумісні вимоги можна виконати одночасно.

Тепер побудуємо граф на білках.

З'єднаємо дві білки ребром, якщо існують два падіння горіхів, одне з яких зачіпає першу білку, а інше — другу, і відповідні вимоги є несумісними.

Тоді множину білок можна врятувати одночасно тоді й лише тоді, коли вона є незалежною множиною в цьому графі.

Отже, задача зводиться до знаходження максимальної незалежної множини в графі з не більш ніж $44$ вершинами.

Тепер побудуємо цей граф ефективно.

Спочатку відсортуємо всі падіння за часом і об'єднаємо всі падіння з однаковим часом в одну бітову маску.

Під час обробки моментів часу зліва направо нехай $l a s t_{i}$ last_i — останній момент часу, коли білку $i$ зачепило падіння.

Нехай поточний момент часу дорівнює $t$ , і білка $j$ зараз потрапляє під падіння.

Для іншої білки $i$ серед усіх попередніх падінь, які її зачіпали, достатньо розглянути лише останнє.

Справді, останнє падіння має найменшу різницю часу з $t$ , а тому задає найсильніше обмеження. Якщо воно сумісне з поточним падінням, то всі попередні падіння також будуть сумісними.

Нехай останнє падіння, яке зачіпало білку $i$ , відбулося в момент $l a s t_{i}$ last_i.

Тоді білки $i$ та $j$ несумісні, якщо

$∣ x_{i} - x_{j} ∣ > w + (t - l a s t_{i}) .$ |x_i-x_j|>w+(t-last_i).

Для фіксованої білки $i$ всі білки, які зараз потрапляють під падіння та конфліктують з нею, знаходяться поза відрізком

$[x_{i} - (w + t - l a s t_{i}), x_{i} + (w + t - l a s t_{i})] .$ [x_i-(w+t-last_i),x_i+(w+t-last_i)].

Оскільки координати $x_{i}$ x_i відсортовані, межі цього відрізка можна знайти за допомогою бінарного пошуку, після чого додати всі конфліктні білки за допомогою бітових масок.

Після обробки всіх моментів часу отримаємо граф несумісності.

Тепер потрібно знайти максимальну незалежну множину в графі з $n \leq 44$ n\le44 вершинами.

Використаємо meet-in-the-middle.

Розіб'ємо вершини на дві частини розміру не більше $22$ .

Для кожної підмножини $ma s k$ другої половини нехай $b es t [ma s k]$ best[mask] — максимальний розмір незалежної множини, яка повністю міститься в цій підмножині.

Виберемо довільну вершину $v$ з $ma s k$ .

Є два варіанти.

Не брати $v$ :

$b es t [ma s k] = b es t [ma s k ∖ {v}] .$ best[mask]=best[mask\setminus\{v\}].

Або взяти $v$ . Тоді всіх її сусідів потрібно видалити:

$b es t [ma s k] = 1 + b es t [(ma s k ∖ {v}) ∖ N (v)] .$ best[mask] = 1+ best[(mask\setminus\{v\})\setminus N(v)].

Беремо максимум із цих двох варіантів.

Тепер переберемо всі підмножини першої половини.

Для кожної підмножини перевіримо, чи є вона незалежною.

Якщо так, знайдемо всі вершини другої половини, які суміжні хоча б з однією вибраною вершиною. Такі вершини використовувати не можна.

Після цього додамо найкращу незалежну множину серед усіх дозволених вершин другої половини.

Максимум серед усіх підмножин першої половини і буде відповіддю.

Часова складність побудови графа — $O (q lo g q + q n lo g n)$ O(q\log q+qn\log n).

Meet-in-the-middle працює за $O (2^{n /2})$ O(2^{n/2}).

Загальна часова складність дорівнює

$O (q lo g q + q n lo g n + 2^{n /2}) .$ O(q\log q+qn\log n+2^{n/2}).

Просторова складність — $O (q + 2^{n /2})$ O(q+2^{n/2}).

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl '\n'
#define pb push_back

const ll clasik = 2e5+17;
const int MASK = (1<<22);

struct fall_event {
    ll t;
    ull mask;
};

ll x[50] , lastt[50];

ull gr[50];

int g2[25];
int banMask[MASK];
int bestMask[MASK];
int goodMask[MASK];

signed main() {
    speed;

    ll n , q , w;

    cin>>n>>q>>w;

    for (int i = 1 ; i<=n ; i++) cin>>x[i];

    vector<fall_event> ev;

    ev.reserve(q);

    for (int z = 0 ; z<q ; z++) {
        ll t , l , r;

        cin>>t>>l>>r;

        ll L = lower_bound(x+1 , x+n+1 , l)-x;
        ll R = upper_bound(x+1 , x+n+1 , r)-x-1;

        ull mask = 0;

        if (L <= R) {
            ll len = R-L+1;

            mask = ((1ULL<<len)-1)<<(L-1);
        }

        ev.pb({t , mask});
    }

    sort(ev.begin() , ev.end() , [](fall_event A , fall_event B) {
        return A.t < B.t;
    });

    for (int i = 1 ; i<=n ; i++) {
        lastt[i] = -1;
    }

    ull all = (1ULL<<n)-1;

    for (int z = 0 ; z<q ; ) {
        int j = z;

        ll t = ev[z].t;

        ull cur = 0;

        while(j < q && ev[j].t == t) {
            cur |= ev[j].mask;
            j++;
        }

        if (cur) {

            for (int i = 1 ; i<=n ; i++) {
                if (cur&(1ULL<<(i-1))) {
                    lastt[i] = t;
                }
            }

            for (int i = 1 ; i<=n ; i++) {
                if (lastt[i] == -1) continue;

                ll dist = w+t-lastt[i];

                ll L = lower_bound(
                    x+1 , x+n+1 , x[i]-dist
                )-x;

                ll R = upper_bound(
                    x+1 , x+n+1 , x[i]+dist
                )-x;

                ull bad = 0;

                if (L > 1) {
                    bad |= (1ULL<<(L-1))-1;
                }

                if (R <= n) {
                    bad |= all^((1ULL<<(R-1))-1);
                }

                gr[i] |= cur&bad;
            }
        }

        z = j;
    }

    for (int i = 1 ; i<=n ; i++) {
        for (int j = 1 ; j<=n ; j++) {
            if (gr[i]&(1ULL<<(j-1))) {
                gr[j] |= (1ULL<<(i-1));
            }
        }
    }

    int n1 = n/2;
    int n2 = n-n1;

    int all2 = (1<<n2)-1;

    for (int v = 0 ; v<n2 ; v++) {
        g2[v] = (gr[n1+v+1]>>n1)&all2;
    }

    int sz2 = (1<<n2);

    bestMask[0] = 0;

    for (int mask = 1 ; mask<sz2 ; mask++) {
        int v = __builtin_ctz(mask);

        int rest = mask^(1<<v);

        int take =
            rest&(~g2[v])&all2;

        bestMask[mask] = max(
            bestMask[rest],
            1+bestMask[take]
        );
    }

    ll ans = bestMask[all2];

    goodMask[0] = 1;
    banMask[0] = 0;

    int sz1 = (1<<n1);

    for (int mask = 1 ; mask<sz1 ; mask++) {
        int v = __builtin_ctz(mask);

        int prev = mask^(1<<v);

        goodMask[mask] =
            goodMask[prev] &&
            ((gr[v+1]&(ull)prev) == 0);

        banMask[mask] =
            banMask[prev] |
            ((gr[v+1]>>n1)&all2);

        if (!goodMask[mask]) continue;

        int can =
            all2&(~banMask[mask]);

        ans = max(
            ans,
            (ll)__builtin_popcount(mask)
            +(ll)bestMask[can]
        );
    }

    cout<<ans<<endl;

    return 0;
}

C++