Submission #104558

#	Time	Username	Problem	Language	Result	Execution time	Memory
104558		minhtung0404	Two Antennas (JOI19_antennas)	C++17	100 / 100	853 ms	61704 KiB

antennas

#include<bits/stdc++.h>
#define int long long
const int N = 2e5 + 5;
const int inf = 2e9;
using namespace std;

struct query{
    int l, r, id;

    bool operator < (const query&a) const{
        return r < a.r;
    }
} qu[N];

vector <int> mv[2][N];
typedef pair <int, int> ii;
ii it[N << 2], lazy[N << 2];
int n, q, Max[N << 2], h[N], a[N], b[N], ans[N];

ii up(ii a, ii b){
    return ii(min(a.first, b.first), max(a.second, b.second));
}

void dolazy(int i, int l, int r){
    if (lazy[i] == ii(inf, -inf)) return;
    if (l != r){
        lazy[i << 1] = up(lazy[i << 1], lazy[i]);
        lazy[i << 1 | 1] = up(lazy[i << 1 | 1], lazy[i]);
    }
    Max[i] = max(Max[i], max(lazy[i].second - it[i].first, it[i].second - lazy[i].first));
    lazy[i] = ii(inf, -inf);
}

void update_h(int i, int l, int r, int pos, ii val){
    dolazy(i, l, r);
    if (l > pos || pos > r || l > r) return;
    if (l == r){
        it[i] = val;
        return;
    }
    int mid = (l + r) >> 1;
    update_h(i << 1, l, mid, pos, val); update_h(i << 1 | 1, mid+1, r, pos, val);
    it[i] = up(it[i << 1], it[i << 1 | 1]);
}

void update(int i, int l, int r, int L, int R, int val){
    dolazy(i, l, r);
    if (L > r || l > R || l > r || L > R) return;
    if (L <= l && r <= R){
        lazy[i] = ii(val, val);
        dolazy(i, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    update(i << 1, l, mid, L, R, val); update(i << 1 | 1, mid+1, r, L, R, val);
    Max[i] = max(Max[i << 1], Max[i << 1 | 1]);
}

int get(int i, int l, int r, int L, int R){
    dolazy(i, l, r);
    if (L > r || l > R || l > r || L > R) return -1;
    if (L <= l && r <= R) return Max[i];
    int mid = (l + r) >> 1;
    return max(get(i << 1, l, mid, L, R), get(i << 1 | 1, mid+1, r, L, R));
}

void add(int pos){
    int l = max(1LL, pos - b[pos]), r = max(0LL, pos - a[pos]);

    for (auto p : mv[0][pos]) update_h(1, 1, n, p, ii(h[p], h[p]));
    for (auto p : mv[1][pos]) update_h(1, 1, n, p, ii(inf, -inf));

    update(1, 1, n, l, r, h[pos]);

    l = min(n+1, pos + a[pos]), r = min(n, pos + b[pos]);
    mv[0][l].push_back(pos);
    mv[1][r+1].push_back(pos);
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    for (int i = 0; i < N << 2; i++) it[i] = lazy[i] = ii(inf, -inf), Max[i] = -1;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i] >> a[i] >> b[i];
    cin >> q;
    for (int i = 1; i <= q; i++){
        cin >> qu[i].l >> qu[i].r;
        qu[i].id = i;
    }
    sort(qu+1, qu+1+q);
    int cur = 1;
    for (int i = 1; i <= q; i++){
        while (cur <= qu[i].r) add(cur++);
        ans[qu[i].id] = get(1, 1, n, qu[i].l, qu[i].r);
    }
    for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

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