Submission #1268897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268897		noyancanturk	Two Antennas (JOI19_antennas)	C++20	22 / 100	230 ms	32104 KiB

antennas

#include<bits/stdc++.h>
using namespace std;

#define pb push_back

const int lim=2e5+100;

int n,q;

int h[lim],a[lim],b[lim];
int l[lim],r[lim];
int ans[lim];
vector<int>v[lim];

vector<int>come[lim],go[lim];

struct{
  int tree[4*lim],mini[4*lim],maxi[4*lim],minl[4*lim],maxl[4*lim];
  void init(){
    for(int i=0;i<4*n;i++){
      tree[i]=-1;
      mini[i]=minl[i]=INT_MAX;
      maxi[i]=maxl[i]=INT_MIN;
    }
  }
  void push(int node,int l,int r){
    if((mini[node]^INT_MAX)&&(minl[node]^INT_MAX)){
      tree[node]=max({tree[node],maxl[node]-mini[node],maxi[node]-minl[node]});
    }
    if(minl[node]^INT_MAX){
      if(l^r){
        int child=node<<1;
        minl[child]=min(minl[child],minl[node]);
        minl[child|1]=min(minl[child|1],minl[node]);
        maxl[child]=max(maxl[child],maxl[node]);
        maxl[child|1]=max(maxl[child|1],maxl[node]);
      }
      minl[node]=INT_MAX;
      maxl[node]=INT_MIN;
    }
  }
  int P;
  void update(int l,int r,int node){
    push(node,l,r);
    if(l==r){
      mini[node]^=INT_MAX^h[l];
      maxi[node]^=INT_MIN^h[l];
      return;
    }
    int mid=l+r>>1,child=node<<1;
    if(P<=mid)update(l,mid,child),push(child|1,mid+1,r);
    else push(child,l,mid),update(mid+1,r,child|1);
    mini[node]=min(mini[child],mini[child|1]);
    maxi[node]=max(maxi[child],maxi[child|1]);
  }
  void update(int p){
    P=p;
    update(0,n-1,1);
  }
  void insert(int l,int r,int node){
    if(P+a[P]<=l&&r<=P+b[P]){
      minl[node]=min(minl[node],h[P]);
      maxl[node]=max(maxl[node],h[P]);
      push(node,l,r);
      return;
    }
    push(node,l,r);
    if(r<P+a[P]||P+b[P]<l)return;
    int mid=l+r>>1,child=node<<1;
    insert(l,mid,child),insert(mid+1,r,child|1);
    tree[node]=max(tree[child],tree[child|1]);
  }
  void insert(int p){
    P=p;
    insert(0,n-1,1);
  }
  int ANS;
  void query(int l,int r,int node){
    if(P<l)return;
    push(node,l,r);
    if(r<=P){
      // cerr<<"took "<<node<<' '<<l<<' '<<r<<' '<<tree[node]<<'\n';
      ANS=max(ANS,tree[node]);
      return;
    }
    int mid=l+r>>1,child=node<<1;
    query(l,mid,child),query(mid+1,r,child|1);
  }
  int query(int p){
    P=p,ANS=-1;
    query(0,n-1,1);
    return ANS;
  }
}st;

int main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>h[i]>>a[i]>>b[i];
  }
  cin>>q;
  for(int i=0;i<q;i++){
    cin>>l[i]>>r[i];
    l[i]--,r[i]--;
    v[l[i]].pb(i);
  }
  for(int i=0;i<n;i++){
    come[max(0,i-a[i])].pb(i);
    go[max(0,i-b[i])].pb(i);
  }
  st.init();
  for(int i=n-1;0<=i;i--){
    // cerr<<"at "<<i<<'\n';
    for(int j:come[i]){
      st.update(j);
    }
    if(i+a[i]<n){
      st.insert(i);
    }
    for(int j:v[i]){
      // cerr<<"ask "<<j<<' '<<l[j]<<' '<<r[j]<<'\n';
      ans[j]=st.query(r[j]);
    }
    for(int j:go[i]){
      st.update(j);
    }
    // cerr<<'\n';
  }
  for(int i=0;i<q;i++){
    cout<<ans[i]<<'\n';
  }
}

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