Submission #579085

#	Time	Username	Problem	Language	Result	Execution time	Memory
579085		Lucpp	Two Antennas (JOI19_antennas)	C++17	35 / 100	388 ms	19848 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;

struct Seg{
    vector<int> Smi, Sma;
    int cap;
    void init(int n){
        for(cap = 1; cap < n; cap *= 2);
        Smi.resize(2*cap, INF);
        Sma.resize(2*cap);
    }
    void upd(int i, int v){
        i += cap;
        if(v > 0) Smi[i] = Sma[i] = v;
        else Smi[i] = INF, Sma[i] = 0;
        while(i > 1){
            i /= 2;
            Smi[i] = min(Smi[2*i], Smi[2*i+1]);
            Sma[i] = max(Sma[2*i], Sma[2*i+1]);
        }
    }
    pair<int, int> qry(int l, int r, int a, int b, int i){
        if(l <= a && b <= r) return {Smi[i], Sma[i]};
        if(r < a || b < l) return {INF, 0};
        int m = (a+b)/2;
        auto [mi1, ma1] = qry(l, r, a, m, 2*i);
        auto [mi2, ma2] = qry(l, r, m+1, b, 2*i+1);
        return {min(mi1, mi2), max(ma1, ma2)};
    }
    pair<int, int> qry(int l, int r){return qry(l, r, 1, cap, 1);}
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n;
    vector<int> h(n), a(n), b(n);
    for(int i = 0; i < n; i++) cin >> h[i] >> a[i] >> b[i];

    vector<vector<int>> memo((n<=2000?n:1), vector<int>(n));
    for(int L = 0; L < (n<=2000?n:1); L++){
        Seg seg;
        seg.init(n);
        vector<vector<pair<int, int>>> todo(n);
        int ans = -1;
        for(int i = L; i < n; i++){
            for(auto [j, v] : todo[i]){
                seg.upd(j, v);
            }
            if(i+a[i]<n) todo[i+a[i]].emplace_back(i, h[i]);
            if(i+b[i]+1<n) todo[i+b[i]+1].emplace_back(i, 0);
            int l = max(0, i-b[i]);
            int r = max(-1, i-a[i]);
            if(r != -1){
                auto [mi, ma] = seg.qry(l+1, r+1);
                ans = max(ans, max(h[i]-mi, ma-h[i]));
            }
            memo[L][i] = ans;
        }
    }

    cin >> q;
    for(int i = 0; i < q; ++i){
        int l, r;
        cin >> l >> r;
        cout << memo[l-1][r-1] << "\n";
    }
}

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