제출 #1170155

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170155		M_W_13	Two Antennas (JOI19_antennas)	C++20	35 / 100	122 ms	19940 KiB

antennas

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
const int MAXN = 1 << 18;
ll seg1[2 * MAXN];
ll seg[2 * MAXN][2];

void upd2(int v, int c, ll x) {
    v += MAXN;
    seg[v][c] = x;
    v /= 2;
    while (v > 0) {
        seg[v][c] = max(seg[2 * v][c], seg[2 * v + 1][c]);
        v /= 2;
    }
}

ll query2(int l, int r, int c) {
    l += MAXN;
    r += MAXN;
    ll ans = -1e18;
    while (l < r) {
        if (l % 2 == 1) {
            ans = max(ans, seg[l][c]);
            l++;
        }
        if (r % 2 == 0) {
            ans = max(ans, seg[r][c]);
            r--;
        }
        l /= 2;
        r /= 2;
    }
    if (l == r) {
        ans = max(ans, seg[l][c]);
    }
    return ans;
}

void upd(int v, ll x) {
    v += MAXN;
    seg1[v] = max(seg1[v], x);
    v /= 2;
    while (v > 0) {
        seg1[v] = max(seg1[2 * v], seg1[2 * v + 1]);
        v /= 2;
    }
}

ll query(int l, int r) {
    l += MAXN;
    r += MAXN;
    ll ans = -1;
    while (l < r) {
        if (l % 2 == 1) {
            ans = max(ans, seg1[l]);
            l++;
        }
        if (r % 2 == 0) {
            ans = max(ans, seg1[r]);
            r--;
        }
        l /= 2;
        r /= 2;
    }
    if (l == r) {
        ans = max(ans, seg1[l]);
    }
    return ans;
}

struct ant {
    ll h;
    int a, b;
};

ant T[MAXN];

struct pr {
    int l, r;
    int nr;
};

ll spr(int x, int y) {
    if ((x + T[x].a <= y) && (x + T[x].b >= y) && (y - T[y].a >= x) && (y - T[y].b <= x)) {
        return abs(T[x].h - T[y].h);
    }
    return -1;
}

bool por(pr a, pr b) {
    return a.l < b.l;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    rep(i, 2 * MAXN) {
        seg1[i] = -1;
        seg[i][0] = -1e18;
        seg[i][1] = -1e18;
    }
    int n;
    cin >> n;
    rep(i, n) {
        cin >> T[i].h >> T[i].a >> T[i].b;
    }
    if (n <= 2000) {
        int q;
        cin >> q;
        pr pyt[q];
        rep(i, q) {
            cin >> pyt[i].l >> pyt[i].r;
            pyt[i].l = pyt[i].l - 1;
            pyt[i].r = pyt[i].r - 1;
            pyt[i].nr = i;
        }
        ll odp[q];
        sort(pyt, pyt + q, por);
        int v = n - 1;
        for (int i = q - 1; i >= 0; i--) {
            while (v >= pyt[i].l) {
                for (int w = v + 1; w < n; w++) {
                    upd(w, spr(v, w));
                }
                v--;
            }
            odp[pyt[i].nr] = query(pyt[i].l, pyt[i].r);
        }
        rep(i, q) {
            cout << odp[i] << " ";
        }
        cout << '\n';
    }
    else {
        int q;
        cin >> q;
        ll odp = -1;
        vector<pair<int, int>> zmiany;
        rep(i, n) {
            zmiany.pb({i + T[i].a, i});
            zmiany.pb({i + T[i].b + 1, i});
        }
        bool czyjest[n];
        rep(i, n) {
            czyjest[i] = false;
        }
        sort(zmiany.begin(), zmiany.end());
        int it = 0;
        int sz = zmiany.size();
        rep(i, n) {
            while (it < sz && zmiany[it].st == i) {
                int v = zmiany[it].nd;
                if (czyjest[v]) {
                    upd2(v, 0, -1e18);
                    upd2(v, 1, -1e18);
                    czyjest[v] = false;
                }
                else {
                    upd2(v, 1, T[v].h);
                    upd2(v, 0, -T[v].h);
                    czyjest[v] = true;
                }
                it++;
            }
            int l = i - T[i].b;
            int r = i - T[i].a;
            if (r >= 0) {
                l = max(0, l);
                // cout << "i = " << i << " max = " << query2(l, r, 1) << " " << query2(l, r, 0) << '\n';
                odp = max(odp, max(T[i].h + query2(l, r, 0), query2(l, r, 1) - T[i].h));
            }
        }
        cout << odp << '\n';
    }
    return 0;
}

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