Submission #993884

#	Time	Username	Problem	Language	Result	Execution time	Memory
993884		vladilius	Two Antennas (JOI19_antennas)	C++17	22 / 100	156 ms	31292 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
const int inf = 1e9 + 5;
 
struct ST{
    vector<int> t;
    int n, un; bool type;
    ST(int ns, bool ts){
        n = ns; type = ts;
        un = inf * ts;
        t.assign(4 * n, un);
    }
    int f(int x, int y){
        if (type){
            return min(x, y);
        }
        return max(x, y);
    }
    
    int get(int v, int tl, int tr, int& l, int& r){
        if (l > tr || r < tl) return un;
        if (l <= tl && tr <= r) return t[v];
        int tm = (tl + tr) / 2, vv = 2 * v;
        return f(get(vv, tl, tm, l, r), get(vv + 1, tm + 1, tr, l, r));
    }
    int get(int l, int r){
        return get(1, 1, n, l, r);
    }
    void upd(int v, int tl, int tr, int& p, int& k){
        if (tl == tr){
            t[v] = k;
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (p <= tm){
            upd(vv, tl, tm, p, k);
        }
        else {
            upd(vv + 1, tm + 1, tr, p, k);
        }
        t[v] = f(t[vv], t[vv + 1]);
    }
    void upd(int p, int k){
        upd(1, 1, n, p, k);
    }
    void res(int p){
        upd(p, un);
    }
};
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n; cin>>n;
    vector<int> h(n + 1), a(n + 1), b(n + 1);
    pii rr[n + 1][2];
    vector<array<int, 3>> all;
    for (int i = 1; i <= n; i++){
        cin>>h[i]>>a[i]>>b[i];
        int l = i - b[i], r = i - a[i];
        if (r >= 1){
            rr[i][0] = {max(1, l), r};
        }
        l = i + a[i]; r = i + b[i];
        if (l <= n){
            rr[i][1] = {l, min(n, r)};
            all.pb({l, min(n, r), i});
        }
    }
    
    vector<int> st[n + 1], end[n + 1];
    for (auto p: all){
        st[p[0]].pb(p[2]);
        end[p[1]].pb(p[2]);
    }
    
    ST T1(n, 1), T2(n, 0); // T1 - min, T2 - max
    int out = 0;
    for (int i = 1; i <= n; i++){
        for (int j: st[i]){
            T1.upd(j, h[j]);
            T2.upd(j, h[j]);
        }
        
        int h1 = T1.get(rr[i][0].ff, rr[i][0].ss);
        int h2 = T2.get(rr[i][0].ff, rr[i][0].ss);
        
        // cout<<h1<<" "<<h2<<"\n";
        
        if (h1 < inf) out = max(out, abs(h[i] - h1));
        if (h2 > 0) out = max(out, abs(h[i] - h2));
        
        for (int j: end[i]){
            T1.res(j);
            T2.res(j);
        }
    }
    
    cout<<out<<"\n";
 
    // (i -> j): a[i] <= abs(i - j) <= b[i]
    // (j -> i): a[j] <= abs(j - i) <= b[j]
    // i <-> j: abs(i - j) є [a[i], b[i]], [a[j], b[j]]
}

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