Submission #1266261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266261		dhuyyyy	Two Antennas (JOI19_antennas)	C++20	22 / 100	325 ms	38840 KiB

antennas

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using ii = pair<int,int>;
using pii = pair<int,ii>;
using aa = array<int,4>;

const int N = 2e5+5;
const int INF = 1e9;
const int MOD = 30013;

int n, q, l, r, h[N], a[N], b[N], ans[N];

vector <int> p[N];

vector <ii> qr[N];

struct SMT{
    int n;
    vector <int> t;
    vector <int> lazy;
    vector <int> st;
    SMT(int _n = 0) : n(_n){
        t.assign((n << 2),-1e18);
        lazy.assign((n << 2),1e18);
        st.assign((n << 2),-1e18);
    }
    void push(int id,int l,int r){
        if (l == r || lazy[id] == 1e18) return;
        for (int i = 0; i <= 1; i++){
            st[id * 2 + i] = max(st[id * 2 + i],t[id * 2 + i] - lazy[id]);
            lazy[id * 2 + i] = min(lazy[id * 2 + i],lazy[id]);
        }
        lazy[id] = 1e18;
    }
    void update(int id,int l,int r,int pos,int val){
        push(id,l,r);
        if (r < pos || l > pos) return;
        if (l == r){
            t[id] = val;
            return;
        }
        int mid = (l + r) >> 1;
        update(id*2,l,mid,pos,val);
        update(id*2+1,mid+1,r,pos,val);
        t[id] = max(t[id*2],t[id*2+1]);
    }
    void update2(int id,int l,int r,int u,int v,int val){
        push(id,l,r);
        if (r < u || l > v) return;
        if (u <= l && r <= v){
            st[id] = max(st[id],t[id] - val);
            lazy[id] = min(lazy[id],val);
            push(id,l,r);
            return;
        }
        push(id,l,r);
        int mid = (l + r) >> 1;
        update2(id*2,l,mid,u,v,val);
        update2(id*2+1,mid+1,r,u,v,val);
        st[id] = max(st[id*2],st[id*2+1]);
    }
    int getmax(int id,int l,int r,int u,int v){
        push(id,l,r);
        if (r < u || l > v) return -1e18;
        if (u <= l && r <= v) return st[id];
        int mid = (l + r) >> 1;
        int t1 = getmax(id*2,l,mid,u,v);
        int t2 = getmax(id*2+1,mid+1,r,u,v);
        return max(t1,t2);
    }
};
void solve(){
    SMT tnm(n+1);
    for (int i = 1; i <= n; i++){
        for (int it : p[i]){
            if (it > 0) tnm.update(1,1,n+1,it,h[it]);
            else tnm.update(1,1,n+1,-it,-1e18);
        }
        if (i - a[i] > 0) tnm.update2(1,1,n+1,max(1LL,i-b[i]),i-a[i],h[i]);
        for (ii it : qr[i]){
            ans[it.se] = max(ans[it.se],tnm.getmax(1,1,n+1,it.fi,i));
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> h[i] >> a[i] >> b[i];
        p[min(n,i+a[i])].push_back(i);
        p[min(n+1,i+b[i]+1)].push_back(-i);
    }
    cin >> q;
    for (int i = 1; i <= q; i++){
        cin >> l >> r;
        qr[r].push_back({l,i});
        ans[i] = -1;
    }
    solve();
    for (int i = 1; i <= n; i++) h[i] *= -1;
    solve();
    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
    return 0;
}

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