제출 #1271518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271518		ac_quan	Two Antennas (JOI19_antennas)	C++20	0 / 100	141 ms	35652 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
#define all(ac) ac.begin(),ac.end()
#define task "tet"
#define fi first
#define se second
#define pii pair<int,int>
#define db long double
#define int long long

struct node {
    int mn, mx;
    node(int mn = 1e18, int mx = -1e18): mn(mn), mx(mx) {}
};

struct segtree {
    int n;
    vector <node> st;
    vector <int> lz, ans;
    segtree(int n) {
        this -> n = n;
        st.assign(4 * n + 1, node());
        lz.assign(4 * n + 1, 0);
        ans.assign(4 * n + 1, -1);
    }

    void down(int id) {
        int x = lz[id];
        if(x == 0) return;
        ans[id << 1] = max(ans[id << 1], max(st[id << 1].mx - x, x - st[id << 1].mn));
        ans[id << 1 | 1] = max(ans[id << 1 | 1], max(st[id << 1 | 1].mx - x, x - st[id << 1 | 1].mn));
        lz[id << 1] = x;
        lz[id << 1 | 1] = x;
        lz[id] = 0;
        return;
    }

    void update(int id, int l, int r, int pos, int w) {
        if(l > pos || r < pos) return;
        if(l == r) {
            st[id].mn = w;
            st[id].mx = w;
            if(w < 0) st[id] = node();
            return;
        }

        int mid = (l + r) >> 1;
        update(id << 1, l, mid, pos, w);
        update(id << 1 | 1, mid + 1, r, pos, w);
        st[id].mx = max(st[id << 1].mx, st[id << 1 | 1].mx);
        st[id].mn = min(st[id << 1].mn, st[id << 1 | 1].mn);
        return;
    }


    void update_range(int id, int l, int r, int u, int v, int w) {
        if(l > v || r < u) return;
        if(l >= u && r <= v) {
            ans[id] = max(ans[id], max(w - st[id].mn, st[id].mx - w));
            lz[id] = w;
            return;
        }

        int mid = (l + r) >> 1;
        down(id);
        update_range(id << 1, l, mid, u, v, w);
        update_range(id << 1 | 1, mid + 1, r, u, v, w);
        ans[id] = max(ans[id << 1], ans[id << 1 | 1]);
        return;
    }

    int get(int id, int l, int r, int u, int v) {
        if(l > v || r < u) return -1;
        if(l >= u && r <= v) return ans[id];

        int mid = (l + r) >> 1;
        down(id);
        return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
    }
};

const int N = 2e5 + 1;
int n;

struct Event {
    int x, y, z;
    bool operator <(const Event o) {return y < o.y;}
    Event(int x = 0, int y = 0, int z = 0): x(x), y(y), z(z) {}
};

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    vector <Event> events[n + 1];
    Event init[n + 1];
    for(int i=1;i<=n;i++) {
        int h, l, r; cin >> h >> l >> r;
        if(i + l <= n) events[i + l].push_back({i, h, 1});
        if(i + r + 1 <= n) events[i + r + 1].push_back({i, h, -1});
        init[i] = {l, r, h};
    }
    vector <Event> qr;

    int Q; cin >> Q;
    for(int i=1;i<=Q;i++) {
        int l, r; cin >> l >> r;
        qr.push_back({l, r, i});
    }

    sort(all(qr));

    segtree sg(n);
    int ans[Q + 1], pos = 1;
    for(auto e:qr) {
        while(pos <= e.y) {
            for(auto d:events[pos]) {
                sg.update(1, 1, n, d.x, d.y * d.z);
            }
            
            auto d = init[pos];
            int l = pos - d.y, r = pos - d.x;
            if(r > 0) sg.update_range(1, 1, n, l, r, d.z);
            pos++;
        }
        ans[e.z] = sg.get(1, 1, n, e.x, e.y);
    }
    
    for(int i=1;i<=Q;i++) cout << ans[i] << '\n';
    return 0;
}

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