Submission #1271673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271673		ac_quan	Two Antennas (JOI19_antennas)	C++20	100 / 100	352 ms	54524 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) {}
    
    bool operator == (const node o) {return o.mn == mn && o.mx == mx;}
};

node dat(node a, node b) {
    return {min(a.mn, b.mn), max(a.mx, b.mx)};
}

struct segtree {
    int n;
    vector <node> st, lz;
    vector <int> ans;
    
    segtree(int n): n(n), ans(4 * n + 1, -1), lz(4 * n + 1, node()), st(4 * n + 1, node()) {}
    
    void down(int id) {
        auto x = lz[id];
        if(x == node()) return;
        
        lz[id << 1] = dat(lz[id << 1], x);
        lz[id << 1 | 1] = dat(lz[id << 1 | 1], x);
        ans[id << 1] = max(ans[id << 1], max(lz[id << 1].mx - st[id << 1].mn, st[id << 1].mx - lz[id << 1].mn));
        ans[id << 1 | 1] = max({ans[id << 1 | 1], lz[id << 1 | 1].mx - st[id << 1 | 1].mn, st[id << 1 | 1].mx - lz[id << 1 | 1].mn});
        
        lz[id] = node();
        return;
    }

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

        int mid = (l + r) >> 1;
        down(id);
        update_point(id << 1, l, mid, pos, w);
        update_point(id << 1 | 1, mid + 1, r, pos, w);
        st[id] = dat(st[id << 1], st[id << 1 | 1]);
        ans[id] = max(ans[id << 1], ans[id << 1 | 1]);
        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) {
            lz[id] = dat(lz[id], {w, w});
            ans[id] = max({ans[id], lz[id].mx - st[id].mn, st[id].mx - lz[id].mn});
            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));
    }
};

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);

    int n; 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_point(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: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65