제출 #579075

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
579075		Lucpp	Two Antennas (JOI19_antennas)	C++17	22 / 100	162 ms	16604 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];
    cin >> q;
    int qL, qR;
    cin >> qL >> qR;

    Seg seg;
    seg.init(n);
    vector<vector<pair<int, int>>> todo(n);
    int ans = -1;
    for(int i = 0; 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) continue;
        auto [mi, ma] = seg.qry(l+1, r+1);
        ans = max(ans, max(h[i]-mi, ma-h[i]));
    }
    cout << ans << "\n";
}

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