제출 #1170132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170132		M_W_13	Two Antennas (JOI19_antennas)	C++20	13 / 100	124 ms	10056 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];

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;
    }
    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 {

    }
    return 0;
}

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