Submission #1077955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077955		azberjibiou	Two Antennas (JOI19_antennas)	C++17	100 / 100	315 ms	44848 KiB

antennas

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=205000;
const int mxM=1557;
const int mxK=60;
const int inf=1e9+7;
struct node{
    int nmin, nmax, maxi;
};
struct segtree{
    node seg[4*mxN];
    pii lazy[4*mxN];
    node mrg(node a, node b){
        node res;
        res.nmin=min(a.nmin, b.nmin);
        res.nmax=max(a.nmax, b.nmax);
        res.maxi=max(a.maxi, b.maxi);
        return res;
    }
    void propagate(int idx){
        seg[2*idx].maxi=max(seg[2*idx].maxi, max(lazy[idx].fi-seg[2*idx].nmin, seg[2*idx].nmax-lazy[idx].se));
        seg[2*idx+1].maxi=max(seg[2*idx+1].maxi, max(lazy[idx].fi-seg[2*idx+1].nmin, seg[2*idx+1].nmax-lazy[idx].se));
        lazy[2*idx].fi=max(lazy[2*idx].fi, lazy[idx].fi);
        lazy[2*idx].se=min(lazy[2*idx].se, lazy[idx].se);
        lazy[2*idx+1].fi=max(lazy[2*idx+1].fi, lazy[idx].fi);
        lazy[2*idx+1].se=min(lazy[2*idx+1].se, lazy[idx].se);
        lazy[idx]=pii(-inf, inf);
    }
    void init(int idx, int s, int e){
        seg[idx].nmin=inf;
        seg[idx].nmax=seg[idx].maxi=-inf;
        lazy[idx]=pii(-inf, inf);
        if(s==e) return;
        int mid=(s+e)/2;
        init(2*idx, s, mid);
        init(2*idx+1, mid+1, e);
    }
    void updp(int idx, int s, int e, int pos, int val){
        if(s==e){
            if(val!=-1) seg[idx].nmin=seg[idx].nmax=val;
            else seg[idx].nmin=inf, seg[idx].nmax=-inf;
            return;
        }
        propagate(idx);
        int mid=(s+e)/2;
        if(pos<=mid) updp(2*idx, s, mid, pos, val);
        else updp(2*idx+1, mid+1, e, pos, val);
        seg[idx].nmax=max(seg[2*idx].nmax, seg[2*idx+1].nmax);
        seg[idx].nmin=min(seg[2*idx].nmin, seg[2*idx+1].nmin);
    }
    void updr(int idx, int s1, int e1, int s2, int e2, int val){
        if(s1>e2 || s2>e1) return;
        if(s2<=s1 && e1<=e2){
            seg[idx].maxi=max(seg[idx].maxi, max(seg[idx].nmax-val, val-seg[idx].nmin));
            lazy[idx].fi=max(lazy[idx].fi, val);
            lazy[idx].se=min(lazy[idx].se, val);
            //printf("s1, e1, maxi=%d %d %d\n", s1, e1, seg[idx].maxi);
            return;
        }
        propagate(idx);
        int mid=(s1+e1)/2;
        updr(2*idx, s1, mid, s2, e2, val);
        updr(2*idx+1, mid+1, e1, s2, e2, val);
        seg[idx].maxi=max(seg[2*idx].maxi, seg[2*idx+1].maxi);
        //printf("s1, e1, maxi=%d %d %d\n", s1, e1, seg[idx].maxi);
    }
    int solv(int idx, int s1, int e1, int s2, int e2){
        if(s2>e1 || s1>e2) return -inf;
        if(s2<=s1 && e1<=e2) return seg[idx].maxi;
        propagate(idx);
        int mid=(s1+e1)/2;
        return max(solv(2*idx, s1, mid, s2, e2), solv(2*idx+1, mid+1, e1, s2, e2));
    }
};
int N, Q;
int H[mxN];
int l[mxN], r[mxN];
vector <array<int, 3>> qry;
segtree T1;
vector <array<int, 3>> cont[mxN];
vector <pii> inout[mxN];
int ans[mxN];
void input(){
    cin >> N;
    for(int i=1;i<=N;i++) cin >> H[i] >> l[i] >> r[i];
    cin >> Q;
    for(int i=0;i<Q;i++){
        int a, b;
        cin >> a >> b;
        qry.push_back(array<int, 3>{a, b, i+1});
    }
}
void make_qry(){
    for(int i=1;i<=N;i++){
        if(i+l[i]<=N) inout[i+l[i]].emplace_back(i, 1);
        if(i+r[i]+1<=N) inout[i+r[i]+1].emplace_back(i, -1);
        if(i-l[i]>=1) cont[i].push_back({max(1, i-r[i]), i-l[i], H[i]});
    }
    sort(all(qry), [](array<int, 3> a, array<int, 3> b){return a[1]<b[1];});
}
void sweep(){
    T1.init(1, 1, N);
    int cur=0;
    for(int i=1;i<=N;i++){
        for(auto [pos, io] : inout[i]){
            if(io==-1) T1.updp(1, 1, N, pos, -1);
            else T1.updp(1, 1, N, pos, H[pos]);
            //printf("pos, val = %d %d\n", pos, (io==-1 ? -1 : H[pos]));
        }
        for(auto [lv, rv, h] : cont[i]){
            T1.updr(1, 1, N, lv, rv, h);
            //printf("lv, rv, h=%d %d %d\n", lv, rv, h);
        }
        while(cur<Q && qry[cur][1]==i){
            ans[qry[cur][2]]=T1.solv(1, 1, N, qry[cur][0], i);
            //printf("idx, l, r=%d %d %d\n", qry[cur][2], qry[cur][0], qry[cur][1]);
            cur++;
        }
    }
}
int main(){
    gibon
    input();
    make_qry();
    sweep();
    for(int i=1;i<=Q;i++) cout << (ans[i]<0 ? -1 : ans[i]) << '\n';
}

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