Submission #1126200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126200		OI_Account	Two Antennas (JOI19_antennas)	C++20	35 / 100	150 ms	34120 KiB

antennas

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 200'000;
const int N2 = 2000;
const ll INF = 100'000'000'000;

int n, q, a[N + 10], b[N + 10];
ll h[N + 10], mx[4 * N + 10], mn[4 * N + 10];
vector<int> st[N + 10], en[N + 10];
ll dp[N2 + 10][N2 + 10], ans = -1;

void readInput() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> h[i] >> a[i] >> b[i];
}

bool conect(int i, int j) {
    int dis = abs(i - j);
    return a[i] <= dis && dis <= b[i];
}

bool good(int i, int j) {
    return conect(i, j) && conect(j, i);
}

void solveSmall() {
    for (int i = 1; i <= n; i++)
        dp[i][i] = -1;
    for (int len = 2; len <= n; len++)
        for (int i = 1, j = len; j <= n; i++, j++) {
            dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            if (good(i, j))
                dp[i][j] = max(dp[i][j], llabs(h[i] - h[j]));
        }
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << dp[l][r] << '\n';
    }
}

pair<ll, ll> get(int st, int en, int id = 1, int l = 1, int r = n + 1) {
    if (en <= l || r <= st)
        return {INF, -INF};
    if (st <= l && r <= en)
        return {mn[id], mx[id]};
    int mid = (l + r) >> 1;
    pair<int, int> p1 = get(st, en, id << 1, l, mid);
    pair<int, int> p2 = get(st, en, id << 1 | 1, mid, r);
    return {min(p1.first, p2.first), max(p1.second, p2.second)};
}

void update(int idx, int id = 1, int l = 1, int r = n + 1) {
    if (l + 1 == r) {
        mn[id] = mx[id] = h[idx];
        return;
    }
    int mid = (l + r) >> 1;
    if (idx < mid)
        update(idx, id << 1, l, mid);
    else
        update(idx, id << 1 | 1, mid, r);
    mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
    mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
}

void updateDel(int idx, int id = 1, int l = 1, int r = n + 1) {
    if (l + 1 == r) {
        mn[id] = INF;
        mx[id] = -INF;
        return;
    }
    int mid = (l + r) >> 1;
    if (idx < mid)
        updateDel(idx, id << 1, l, mid);
    else
        updateDel(idx, id << 1 | 1,  mid, r);
    mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
    mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
}

void build(int id = 1, int l = 1, int r = n + 1) {
    mn[id] = INF;
    mx[id] = -INF;  
    if (l + 1 == r)
        return;
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid, r);
}

void calcVec() {
    for (int i = 1; i <= n; i++) {
        if (i + a[i] <= n) 
            st[i + a[i]].push_back(i);
        if (i + b[i] <= n)
            en[i + b[i]].push_back(i);
    }
}

void updateAns(int i) {
    if (1 <= i - a[i]) {
        int r = i - a[i];
        int l = max(1, i - b[i]);
        pair<ll, ll> p = get(l, r + 1);
        ll tmp = max({-1ll, h[i] - p.first, p.second - h[i]});
        ans = max(ans, tmp);
    }
}

void calcAns() {
    for (int i = 1; i <= n; i++) {
        for (auto id: st[i])
            update(id);
        updateAns(i);
        for (auto id: en[i])
            updateDel(id);
    }
    int l, r;
    cin >> q >> l >> r;
    cout << ans;
}  

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    if (n <= N2) 
        solveSmall();
    else {
        build();
        calcVec();
        calcAns();
    }
    cout.flush();
    return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 65