Submission #947838

#	Time	Username	Problem	Language	Result	Execution time	Memory
947838		phoenix0423	Two Antennas (JOI19_antennas)	C++17	100 / 100	539 ms	58108 KiB

antennas

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
const int maxn = 2e5 + 5;
const int INF = 1e18;
int n, q;
int h[maxn], a[maxn], b[maxn];
vector<pll> qry[maxn], e[maxn * 2];
int ans[maxn];

struct node{
    int ans, mxc;
    int td; 
} st[maxn * 4];

void build(int v = 1, int l = 0, int r = n - 1){
    st[v].ans = st[v].mxc = -INF;
    st[v].td = INF;
    if(l == r) return;
    int m = (l + r) / 2;
    build(v * 2, l, m);
    build(v * 2 + 1, m + 1, r);
}

void cast(int v, int val){
    st[v].td = min(st[v].td, val);
    st[v].ans = max(st[v].ans, st[v].mxc - st[v].td);
}

void push(int v){
    if(st[v].td != INF){
        cast(v * 2, st[v].td);
        cast(v * 2 + 1, st[v].td);
        st[v].td = INF;
    }
}
void pull(int v){
    st[v].mxc = max(st[v * 2].mxc, st[v * 2 + 1].mxc);
    st[v].ans = max(st[v * 2].ans, st[v * 2 + 1].ans);
}

void setc(int pos, int val, int v = 1, int l = 0, int r = n - 1){
    if(l == r){
        st[v].mxc = val;
        st[v].td = INF;
        return;
    }
    push(v);
    int m = (l + r) / 2;
    if(pos <= m) setc(pos, val, v * 2, l, m);
    else setc(pos, val, v * 2 + 1, m + 1, r);
    pull(v);
}

void apply(int l, int r, int val, int v = 1, int L = 0, int R = n - 1){
    if(l > R || r < L) return;
    if(l <= L && r >= R){
        cast(v, val);
        return;
    }
    push(v);
    int m = (L + R) / 2;
    apply(l, r, val, v * 2, L, m);
    apply(l, r, val, v * 2 + 1, m + 1, R);
    pull(v);
}

int get(int l, int r, int v = 1, int L = 0, int R = n - 1){
    if(l > R || r < L) return -INF;
    if(l <= L && r >= R) return st[v].ans;
    push(v);
    int m = (L + R) / 2;
    return max(get(l, r, v * 2, L, m), get(l, r, v * 2 + 1, m + 1, R));
}

void solve(){
    build();
    for(int i = 0; i < n; i++){
        // erase j
        for(auto [x, t] : e[i]){
            if(t == -1) setc(x, -INF);
            else setc(x, h[x]);
        }
        //insert i
        apply(max(0LL, i - b[i]), i - a[i], h[i]);
        //handle qry
        for(auto [l, id] : qry[i]){
            ans[id] = max(ans[id], get(l, i));
        }
    }
}

signed main(void){
    fastio;
    cin>>n;
    for(int i = 0; i < n; i++){
        cin>>h[i]>>a[i]>>b[i];
        e[i + a[i]].eb(i, 1);
        e[i + b[i] + 1].eb(i, -1);
    }
    cin>>q;
    for(int i = 0; i < q; i++){
        int l, r;
        cin>>l>>r;
        l--, r--;
        qry[r].eb(l, i);
    }
    for(int i = 0; i < q; i++) ans[i] = -INF;
    solve();
    for(int i = 0; i < n; i++) h[i] = INF - h[i];
    solve();
    for(int i = 0; i < q; i++) cout<<(ans[i] >= 0 ? ans[i] : -1)<<"\n";
}

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