Submission #1248499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248499		LmaoLmao	Two Antennas (JOI19_antennas)	C++20	100 / 100	519 ms	162652 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 aa = array<double,3>; 
 
const int N = 2e6+5;
const int INF = 1e9;
const int MOD = 1e9+7; 

struct LST{ 
    int S[N],lz[N]; 
    int T[N];
    int ans[N]; 
    void build() {
        for(int i=1;i<N;i++) {
            S[i]=-1;
            lz[i]=1e9;
            T[i]=-1e9;
        }
    }
    void push(int id) {
        S[id*2]=max(S[id*2],T[id*2]-lz[id]);
        S[id*2+1]=max(S[id*2+1],T[id*2+1]-lz[id]);
        lz[id*2]=min(lz[id*2],lz[id]);
        lz[id*2+1]=min(lz[id*2+1],lz[id]);
        lz[id]=1e9;
    }
    void uppos(int id,int l,int r,int pos,int val) {
        push(id);
        if(pos < l || r < pos) return;
        if(l==r) {
            T[id]=val;
            //if(pos==6) cout << S[id] << endl;
            return;
        }
        int mid=l+r >> 1;
        uppos(id*2,l,mid,pos,val);
        uppos(id*2+1,mid+1,r,pos,val);
        T[id]=max(T[id*2],T[id*2+1]);
    }
    
    void upseg(int id,int l,int r,int u,int v,int val) {
        push(id);
        if(v < l || r < u) return;
        if(u<=l && r<=v) {
            S[id]=max(S[id],T[id]-val);
            lz[id]=min(lz[id],val);
            //if(v==5) cout << l << ' ' << r << ' ' << u << ' ' << S[id] << endl;
            return;
        }
        int mid=l+r >> 1;
        upseg(id*2,l,mid,u,v,val);
        upseg(id*2+1,mid+1,r,u,v,val);
        S[id]=max(S[id*2],S[id*2+1]);
        //if(v==5) cout << l << ' ' << r << ' ' << u << ' ' << val << endl;
        //if(id==1) cout << u << ' ' << v << endl;
    } 
    int get(int id,int l,int r,int u,int v) {
        push(id);
        if(v < l || r < u) return -1e9;
        if(u<=l && r<=v) {
            return S[id];
        } 
        int mid=l+r >> 1;
        int t1=get(id*2,l,mid,u,v);
        int t2=get(id*2+1,mid+1,r,u,v);
        //cout << u << ' ' << v << ' ' << S[9] << endl;
        return max(t1,t2);
    }
} S;
int a[N][3]; 
vector<ii> qr[N]; 
vector<int> up[N];
int ans[N];
int n;

void solve() {
    S.build();
    for(int i=1;i<=n;i++) {        
        for(int x:up[i]) {
            if(x>0) {
                S.uppos(1,1,n,x,a[x][0]);
            }
            else {
                S.uppos(1,1,n,-x,-2e9);
            }
            //cout << x <<  ' ';
        }
        if(i-a[i][1]>0) S.upseg(1,1,n,max(1LL,i-a[i][2]),i-a[i][1],a[i][0]);
        //cout << i-a[i][1] << ' ';
        for(ii x:qr[i]) {
            ans[x.se]=max(ans[x.se],S.get(1,1,n,x.fi,i));
        }
        //cout << S.get(1,1,n,1,n) << endl;
    }
    //cout << endl;
}

signed main()
{   
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cin >> n;
    for(int i=1;i<=n;i++) {
        for(int j=0;j<3;j++) {
            cin >> a[i][j];
        } 
        up[i+a[i][1]].push_back(i);
        up[i+a[i][2]+1].push_back(-i); 
    } 
    int q;
    cin >> q;
    for(int i=1;i<=q;i++) {
        int l,r;
        cin >> l >> r;
        qr[r].push_back({l,i}); 
        ans[i]=-1;
    }

    solve();
    for(int i=1;i<=n;i++) {
        a[i][0]=-a[i][0];
    }
    solve();
    for(int i=1;i<=q;i++) {
        cout << ans[i] << '\n';
    }
    return 0; 
}
/*
██╗░░██╗██╗░░██╗░█████╗░███╗░░██╗░██████╗░              ░██████╗██╗██╗░░░██╗                ░█████╗░██╗░░░██╗████████╗███████╗
██║░██╔╝██║░░██║██╔══██╗████╗░██║██╔════╝░              ██╔════╝██║██║░░░██║                ██╔══██╗██║░░░██║╚══██╔══╝██╔════╝
█████═╝░███████║███████║██╔██╗██║██║░░██╗░              ╚█████╗░██║██║░░░██║                ██║░░╚═╝██║░░░██║░░░██║░░░█████╗░░
██╔═██╗░██╔══██║██╔══██║██║╚████║██║░░╚██╗              ░╚═══██╗██║██║░░░██║                ██║░░██╗██║░░░██║░░░██║░░░██╔══╝░░
██║░╚██╗██║░░██║██║░░██║██║░╚███║╚██████╔╝              ██████╔╝██║╚██████╔╝                ╚█████╔╝╚██████╔╝░░░██║░░░███████╗
╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚══╝░╚═════╝░              ╚═════╝░╚═╝░╚═════╝░                ░╚════╝░░╚═════╝░░░░╚═╝░░░╚══════╝
*/

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