Submission #211258

#	Time	Username	Problem	Language	Result	Execution time	Memory
211258		brcode	Two Antennas (JOI19_antennas)	C++14	100 / 100	1587 ms	49528 KiB

antennas

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 2e5+5;
long long seg[4*MAXN];
long long temph[4*MAXN];
long long n,q;
long long lazy[4*MAXN];
long long h[MAXN];
long long a[MAXN];
long long ans[MAXN];
long long b[MAXN];
vector<int> add[MAXN];
vector<int> rem[MAXN];
vector<pair<int,int>> v1[MAXN];
bool nxt = false;
void build(long long curr,long long l,long long r){
    if(l==r){
        seg[curr] =-987654321987654321;
        lazy[curr] =-987654321987654321;
        temph[curr] = 987654321987654321;
        return;
    }
    long long mid = (l+r)/2;
    build(2*curr,l,mid);
    build(2*curr+1,mid+1,r);
    seg[curr] = max(seg[2*curr],seg[2*curr+1]);
    lazy[curr] = max(lazy[2*curr],lazy[2*curr+1]);
    temph[curr] = min(temph[2*curr],temph[2*curr+1]);
}
void pushdown(long long curr,long long l,long long r){
    lazy[2*curr] = max(lazy[curr],lazy[2*curr]);
    lazy[2*curr+1] = max(lazy[curr],lazy[2*curr+1]);
    seg[2*curr] = max(seg[2*curr],lazy[2*curr]-temph[2*curr]);
    seg[2*curr+1] = max(seg[2*curr+1],lazy[2*curr+1]-temph[2*curr+1]);
    lazy[curr] = -987654321987654321;
}
void pointupdate(long long curr,long long l,long long r,long long ind,long long x){
    if(l==r){
        temph[curr] = x;
        lazy[curr] = -987654321987654321;
        return;
    }
    pushdown(curr,l,r);
    long long mid = (l+r)/2;
    if(ind<=mid){
        pointupdate(2*curr,l,mid,ind,x);
    }else{
        pointupdate(2*curr+1,mid+1,r,ind,x);
    }
    seg[curr] = max(seg[2*curr],seg[2*curr+1]);
    temph[curr] = min(temph[2*curr],temph[2*curr+1]);
    if(curr == 4){
        //cout<<ind<<" "<<x<<" "<<temph[curr]<<" "<<temph[2*curr]<<" "<<temph[2*curr+1]<<endl;
    }
}
void rangeupdate(long long curr,long long l,long long r,long long tl,long long tr,long long val){
    if(l>tr||r<tl){
        return;
    }
    if(tl<=l && r<=tr){
        lazy[curr] = max(lazy[curr],val);
        seg[curr] = max(seg[curr],val-temph[curr]);
       // cout<<curr<<" "<<123<<" "<<l<<" "<<r<<" "<<temph[2*2*curr]<<endl;
        return;
    }
    long long mid =(l+r)/2;
    pushdown(curr,l,r);
    rangeupdate(2*curr,l,mid,tl,tr,val);
    rangeupdate(2*curr+1,mid+1,r,tl,tr,val);
    seg[curr] = max(seg[2*curr],seg[2*curr+1]);
}
long long query(long long curr,long long l,long long r,long long tl,long long tr){
  //  cout<<l<<" "<<r<<endl;
    if(l>tr||r<tl){
        return -987654321987654321;
    }
   
    
    if(tl<=l &&r<=tr){
        return seg[curr];
    }
    pushdown(curr,l,r);
    long long mid = (l+r)/2;
    return max(query(2*curr,l,mid,tl,tr),query(2*curr+1,mid+1,r,tl,tr));
}
int main(){
 
    cin>>n;
    for(long long i=1;i<=n;i++){
        cin>>h[i]>>a[i]>>b[i];
       if(a[i]+i<MAXN){
            add[a[i]+i].push_back(i);
       }
       if(b[i]+i+1<MAXN){
            rem[b[i]+i+1].push_back(i);
       }
       //cout<<a[i]+i<<" "<<b[i]+i+1<<endl;
    }
    
    cin>>q;
    for(long long i=1;i<=q;i++){
        ans[i] = -1;
        long long l,r;
        cin>>l>>r;
        v1[r].push_back(make_pair(l,i));
    }
    build(1,1,n);
    // cout<<query(1,1,n,1,2)<<endl;
    for(long long i=1;i<=n;i++){
        
        for(long long x:add[i]){
            
            pointupdate(1,1,n,x,h[x]);
            
        }
        for(long long x:rem[i]){
            
            pointupdate(1,1,n,x,987654321987654321);
        }
        //cout<<123<<endl;
        if(i-a[i]>=1){
            rangeupdate(1,1,n,max((long long)1,i-b[i]),i-a[i],h[i]);
          //  cout<<" "<<max((long long)1,i-b[i])<<" "<<i-a[i]<<" "<<h[i]<<endl;
        }
        for(auto x:v1[i]){
             //
            ans[x.second] = max(ans[x.second],query(1,1,n,x.first,i));
           // cout<<x.first<<" "<<i<<" "<<query(1,1,n,x.first,i)<<endl;
        }
       // cout<<query(1,1,n,1,20)<<endl;
    } 
   
    //reverse
    
//cout<<ans[1]<<endl;
    build(1,1,n);
   // cout<<query(1,1,n,1,2)<<endl;
    for(long long i=1;i<=n;i++){
        h[i] = 1000000000-h[i];
    }
    nxt = true;
       for(long long i=1;i<=n;i++){
        
        for(long long x:add[i]){
            
            pointupdate(1,1,n,x,h[x]);
            
        }
        for(long long x:rem[i]){
            
            pointupdate(1,1,n,x,987654321987654321);
        }
        //cout<<123<<endl;
        if(i-a[i]>=1){
            rangeupdate(1,1,n,max((long long)1,i-b[i]),i-a[i],h[i]);
          //  cout<<" "<<max((long long)1,i-b[i])<<" "<<i-a[i]<<" "<<h[i]<<endl;
        }
        for(auto x:v1[i]){
             //
            ans[x.second] = max(ans[x.second],query(1,1,n,x.first,i));
           // cout<<x.first<<" "<<i<<" "<<query(1,1,n,x.first,i)<<endl;
        }
       // cout<<query(1,1,n,1,20)<<endl;
    } 
    
    for(long long i=1;i<=q;i++){
        cout<<ans[i]<<endl;
    }
}

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