🌱 Free Contest 131 - DISPOINT

🌱 Free Contest 131 - DISPOINT

🔗 Link: https://oj.vnoi.info/problem/fc131_dispoint

📌 Tags: `Math`, `Transformation`, `Implementation`

👤 Writer: @SPyofgame

👥 Contributor: @hhoangcpascal , @mạnh, @dantalion, @Melonade

📋 Content:

Hướng dẫn
Tối ưu
- Code
- Bonus

Hướng dẫn

Đặt

f (p, a, b) = m a x (a \times (x_{p} - x_{q}) + b \times (y_{p} - y_{q}) | q = 1 \dots p)

Ta có

(| x_{p} - x_{q} | + | y_{p} - y_{q} |) = m a x (\pm (x_{p} - x_{q}) \pm (y_{p} - y_{q}))

Nên với mọi

p = 1 \dots n

ta có

m a x (| x_{p} - x_{q} | + | y_{p} - y_{q} |) = m a x (A, B, C, D)

với

{\begin{cases} A = m a x (+ (x_{p} - x_{q}) + (y_{p} - y_{q})) = f (p, + 1, + 1) \\ B = m a x (- (x_{p} - x_{q}) + (y_{p} - y_{q})) = f (p, - 1, + 1) \\ C = m a x (+ (x_{p} - x_{q}) - (y_{p} - y_{q})) = f (p, + 1, - 1) \\ D = m a x (- (x_{p} - x_{q}) - (y_{p} - y_{q})) = f (p, - 1, - 1) \end{cases}

Để tính

f (p, a, b)

ta có thể gán

{\begin{cases} x_{i} := x_{i} \times a \\ y_{i} := y_{i} \times b \end{cases}

trước, sau đó hàm

f (p)

giờ có thể tính như sau:

Ta sắp xếp
$(x_{i}, y_{i})$ theo
$x_{i}$ tăng dần rồi ưu tiên
$y_{i}$ tăng dần
$f (p) = m a x ((x_{p} + y_{p}) - (x_{q} + y_{q}) | q = 1 \dots p) = (x_{p} + y_{p}) - m i n (x_{q} + y_{q} | q = 1 \dots p)$
Để tính phần
$m i n ()$ đó chúng ta có thể sử dụng cấu trúc dữ liệu dạng cây trong
$O (\log p)$ cập nhật và tính kết quả

Tối ưu

Thay vì sài cây, đặt

g (q) = m i n (x_{q} + y_{q} | q = 1 \dots p) = m i n ((x_{q} + y_{q}), g (q - 1))

Lúc này ta có

f (p) = (x_{p} + x_{q}) - g (p - 1)

được tính trong

O (1)

với

O (n)

tiền xử lí

Tuy đã bỏ được phần

O (\log)

trong việc sài cấu trúc dữ liệu, lúc này chúng ta vẫn chưa bỏ được hàm sắp xếp

Rút gọn công thức, với mọi

p = 1 \dots n

, ta có

m a x (| x_{p} - x_{q} | + | y_{p} - y_{q} |) = m a x (A, B, C, D)

với

{\begin{cases} A = f (p, + 1, + 1) = (x_{p} + y_{p}) - m i n (x_{q} + y_{q}) \\ B = f (p, - 1, + 1) = m a x (x_{q} - y_{q}) - (x_{p} - y_{p}) \\ C = f (p, + 1, - 1) = (x_{p} - y_{p}) - m i n (x_{q} - y_{q}) \\ D = f (p, - 1, - 1) = m a x (x_{q} + y_{q}) - (x_{p} + y_{p}) \end{cases}

Đặt

{\begin{cases} s_{i} = x_{i} + y_{i} \\ d_{i} = x_{i} - y_{i} \end{cases}

ta dễ dàng tiền xử lí được

{\begin{cases} m a x (s) \\ m i n (s) \\ m a x (d) \\ m i n (d) \end{cases}

do đó có thể xử lí truy vấn trong

O (1)

Code

Time:
$O (n \log n)$
Space:
$O (n)$
Algo: Transformation, Math, Data Structure, Sorting

hhoangcpascal - Tree Implementation

































































/// hhoangcpascal

#include <iostream>
#include <algorithm>
#define llong long long

using namespace std;

struct Point {
    int x, y, pos;

    bool operator < (const Point &other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
} P[200006];

int sorted[200006], bit[200006], sz;
int n, ans[200006];

void Update(int u, int val) {
    for(; u <= sz; u += (u & (-u))) bit[u] = min(bit[u], val);
}

int Query(int u) {
    int mmin = 1e9;
    for(; u > 0; u -= (u & (-u))) mmin = min(mmin, bit[u]);
    return mmin;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);

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

    for(int s = 1; s <= 4; ++s) {
        for(int i = 1; i <= n; ++i) {
            if (s == 2 || s == 4) P[i].y = -P[i].y;
            else if (s == 3) P[i].x = -P[i].x;
        }

        sort(P+1, P+n+1);

        sz = 0;
        for(int i = 1; i <= n; ++i) sorted[++sz] = P[i].y;

        sort(sorted+1, sorted+sz+1);
        sz = unique(sorted+1, sorted+sz+1) - sorted - 1;

        for(int i = 1; i <= sz; ++i) bit[i] = 1e9;

        for(int i = 1; i <= n; ++i) {
            int y = lower_bound(sorted + 1, sorted + sz + 1, P[i].y) - sorted;

            ans[P[i].pos] = max(ans[P[i].pos], P[i].x + P[i].y - Query(y));
            Update(y, P[i].x + P[i].y);
        }
    }

    for(int i = 1; i <= n; ++i) cout << ans[i] << ' ';
    return 0;
}

SPyofgame - Tree Implementation































































































#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int INF = 0x3f3f3f3f;
const int LIM = 2e5 + 25;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

/// ----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----

struct Point 
{
    int x, y, p;
    Point (int x = 0, int y = 0, int p = 0)
    : x(x), y(y), p(p) {}
};

bool operator < (const Point &a, const Point &b)
{
    return (a.x != b.x) ? (a.x < b.x) : (a.y < b.y);
}

/// ----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----

int t[LIM];
int tsz = 0;
void init(int n)
{
    tsz = n;
    memset(t, +INF, sizeof(t[0]) * (tsz + 1));
}

void update(int p, int v)
{
    for (; p <= tsz; p += p & -p)
        minimize(t[p], v);
}

int query(int p)
{
    int res = +INF;
    for (; p >= 1; p -= p & -p)
        minimize(res, t[p]);

    return res;
}

/// ----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----

int n;
Point a[LIM];
int yset[LIM];
int res[LIM];

int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].x;
    for (int i = 1; i <= n; ++i) cin >> a[i].y;
    for (int i = 1; i <= n; ++i) a[i].p = i;   
    for (int i = 1; i <= n; ++i) res[i] = 0;

    for (int rotation = 1; rotation <= 4; ++rotation)
    {
        if (rotation == 2) for (int i = 1; i <= n; ++i) a[i].y = -a[i].y;
        if (rotation == 3) for (int i = 1; i <= n; ++i) a[i].x = -a[i].x;
        if (rotation == 4) for (int i = 1; i <= n; ++i) a[i].y = -a[i].y;

        sort(a + 1, a + n + 1);
        for (int i = 1; i <= n; ++i) yset[i] = a[i].y;
        sort(yset + 1, yset + n + 1);
        int ysize = unique(yset + 1, yset + n + 1) - (yset + 1);

        init(n + 1);
        for (int i = 1; i <= n; ++i)
        {
            int y = lower_bound(yset + 1, yset + n + 1, a[i].y) - yset;
            maximize(res[a[i].p], a[i].x + a[i].y - query(y));
            update(y, a[i].x + a[i].y);
        }
    }

    for (int i = 1; i <= n; ++i)
        cout << res[i] << " ";

    return 0;
}

Time:
$O (n \log n)$
Space:
$O (n)$
Algo: Transformation, Math, Sorting

Code































































#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int INF = 0x3f3f3f3f;
const int LIM = 2e5 + 25;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

/// ----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----

struct Point 
{
    int x, y, p;
    Point (int x = 0, int y = 0, int p = 0)
    : x(x), y(y), p(p) {}
};

bool operator < (const Point &a, const Point &b)
{
    return (a.x != b.x) ? (a.x < b.x) : (a.y < b.y);
}

/// ----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----

int n;
Point a[LIM];
int res[LIM];
int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].x;
    for (int i = 1; i <= n; ++i) cin >> a[i].y;
    for (int i = 1; i <= n; ++i) a[i].p = i;   
    for (int i = 1; i <= n; ++i) res[i] = 0;

    for (int rotation = 1; rotation <= 4; ++rotation)
    {
        if (rotation == 2) for (int i = 1; i <= n; ++i) a[i].y = -a[i].y;
        if (rotation == 3) for (int i = 1; i <= n; ++i) a[i].x = -a[i].x;
        if (rotation == 4) for (int i = 1; i <= n; ++i) a[i].y = -a[i].y;
        sort(a + 1, a + n + 1);
        
        int g = a[1].x + a[1].y;
        for (int i = 2; i <= n; ++i)
        {
            maximize(res[a[i].p], a[i].x + a[i].y - g);
            minimize(g, a[i].x + a[i].y);
        }
    }

    for (int i = 1; i <= n; ++i)
        cout << res[i] << " ";

    return 0;
}

Time:
$O (n)$
Space:
$O (n)$
Algo: Transformation, Math, Implementation

Code









































#include <algorithm>
#include <iostream>

using namespace std;

const int LIM = 2e5 + 25;

int n;
int x[LIM];
int y[LIM];
int Sum[LIM];
int Dif[LIM];
int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);

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

    for (int i = 1; i <= n; ++i)
    {
        Sum[i] = x[i] + y[i];
        Dif[i] = x[i] - y[i];
    }

    int maxSum = *max_element(Sum + 1, Sum + n + 1);
    int minSum = *min_element(Sum + 1, Sum + n + 1);
    int maxDif = *max_element(Dif + 1, Dif + n + 1);
    int minDif = *min_element(Dif + 1, Dif + n + 1);

    for (int i = 1; i <= n; ++i)
    {
        int desSum = max(maxSum - Sum[i], Sum[i] - minSum);
        int desDif = max(maxDif - Dif[i], Dif[i] - minDif);
        cout << max(desSum, desDif) << " ";
    }

    return 0;
}

Bonus

Với trường hợp cho
$q$ truy vấn
$(x_{0}, y_{0})$ và tìm đường đi taxicab xa nhất tới một điêm trong
$n$ điểm cho trước thì bạn làm được không ?

🔗 Link: https://oj.vnoi.info/problem/fc131_dispoint

📌 Tags: Math, Transformation, Implementation

👤 Writer: @SPyofgame

👥 Contributor: @hhoangcpascal , @mạnh, @dantalion, @Melonade

📋 Content:

Hướng dẫn

Tối ưu

Code

Bonus

Read more

🌱 Problem_name

🌱 DP SOS

🌱 Tyrpese Project

🌱 Tyrpese Project

📌 Tags: `Math`, `Transformation`, `Implementation`