Submission #1295968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295968		hanguyendanghuy	Two Antennas (JOI19_antennas)	C++20	100 / 100	507 ms	48292 KiB

antennas

#pragma GCC optimize("O3")
#pragma GCC optimize("O1")
#pragma GCC optimize("O1")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

#include <bits/stdc++.h>
using namespace std;
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
#define si size()
#define fi first
#define se second
#define ll long long
#define sr sort
#define pb push_back
#define all(x) x.begin(),x.end()
constexpr ll MAXN=2e5+5,INF=1e18,MOD=1e9+7,MAXV=1e4+1;
ll n,m,i,j,k,p,dem,t,H[MAXN],ans[MAXN],A[MAXN],B[MAXN];
struct h{
  ll id,a;
} st[MAXN],en[MAXN];
struct mt{
  ll l,r,id;
} q[MAXN];
bool cmp(h x,h y){
  return x.a<y.a;
}
bool cmp1(mt x,mt y){
  return x.r<y.r;
}
struct seg{
  ll b[4*MAXN];
  void build(ll in,ll l,ll r){
    if(l==r)
      b[in]=-INF;
    else{
      ll m=(l+r)/2;
      build(in*2,l,m);
      build(in*2+1,m+1,r);
      b[in]=max(b[in*2],b[in*2+1]);
    }
  }
  void update(ll in,ll l,ll r,ll pos,ll val){
    if(l>pos||r<pos) return;
    else if(l==r){
      b[in]=max(b[in],val);
    }
    else{
      ll m=(l+r)/2;
      update(in*2,l,m,pos,val);
      update(in*2+1,m+1,r,pos,val);
      b[in]=max(b[in*2],b[in*2+1]);
    }
  }
  ll get(ll in,ll l,ll r,ll l1,ll r1){
    if(l>r1||r<l1) return -INF;
    else if(l>=l1&&r<=r1) return b[in];
    else{
      ll m=(l+r)/2;
      return max(get(in*2,l,m,l1,r1),get(in*2+1,m+1,r,l1,r1));
    }
  }
} segans;
struct segsum{
  ll base[4*MAXN],upval[4*MAXN],ans[4*MAXN];
  void down(ll in){
    ll t=upval[in];
    ans[in*2]=max(ans[in*2],t+base[in*2]);
    ans[in*2+1]=max(ans[in*2+1],t+base[in*2+1]);
    upval[in*2]=max(upval[in*2],t);
    upval[in*2+1]=max(upval[in*2+1],t);
    ans[in]=max(ans[in*2],ans[in*2+1]);
    upval[in]=-INF;
  }
  void build(ll in,ll l,ll r){
    if(l==r)
      base[in]=upval[in]=ans[in]=-INF;
    else{
      ll m=(l+r)/2;
      build(in*2,l,m);
      build(in*2+1,m+1,r);
      ans[in]=-INF;
      upval[in]=-INF;
      base[in]=-INF;
    }
  }
  void update(ll in,ll l,ll r,ll l1,ll r1,ll val){
    if(l>r1||r<l1) return;
    else if(l>=l1&&r<=r1){
      upval[in]=max(upval[in],val);
      ans[in]=max(ans[in],base[in]+val);
    }
    else{
      ll m=(l+r)/2;
      down(in);
      update(in*2,l,m,l1,r1,val);
      update(in*2+1,m+1,r,l1,r1,val);
      base[in]=max(base[in*2],base[in*2+1]);
      ans[in]=max(ans[in*2],ans[in*2+1]);
    }
  }
  void update1(ll in,ll l,ll r,ll pos,ll val){
    if(l>pos||r<pos) return;
    else if(l==r){
      segans.update(1,1,n,pos,ans[in]);
      base[in]=val;
      ans[in]=-INF;
    }
    else{
      ll m=(l+r)/2;
      down(in);
      update1(in*2,l,m,pos,val);
      update1(in*2+1,m+1,r,pos,val);
      base[in]=max(base[in*2],base[in*2+1]);
      ans[in]=max(ans[in*2],ans[in*2+1]);
    }
  }
  ll get(ll in,ll l,ll r,ll l1,ll r1){
    if(l>r1||r<l1) return -INF;
    else if(l>=l1&&r<=r1) return ans[in];
    else{
      ll m=(l+r)/2;
      down(in);
      return max(get(in*2,l,m,l1,r1),get(in*2+1,m+1,r,l1,r1));
    }
  }
} seg1,seg2;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  // freopen("test.INP","r",stdin);
  // freopen("test.ac","w",stdout);
  cin>>n;
  for(i=1;i<=n;i++){
    ll l,r;
    cin>>H[i]>>l>>r;
    A[i]=l;
    B[i]=r;
    st[i].id=en[i].id=i;
    st[i].a=i+l;
    en[i].a=i+r;
  }
  cin>>m;
  for(i=1;i<=m;i++){
    cin>>q[i].l>>q[i].r;
    q[i].id=i;
  }
  sort(st+1,st+n+1,cmp);
  sort(en+1,en+n+1,cmp);
  sort(q+1,q+m+1,cmp1);
  segans.build(1,1,n);
  seg1.build(1,1,n);
  seg2.build(1,1,n);
  ll curst=1,curen=1,curq=1;
  for(i=1;i<=n;i++){
    while(curst<=n&&st[curst].a==i){
      ll id=st[curst].id;
      seg1.update1(1,1,n,id,H[id]);
      seg2.update1(1,1,n,id,-H[id]);
      curst++;
    }
    if(A[i]<i){
      seg1.update(1,1,n,max(1ll,i-B[i]),max(1ll,i-A[i]),-H[i]);
      seg2.update(1,1,n,max(1ll,i-B[i]),max(1ll,i-A[i]),H[i]);
    }
    while(curq<=m&&q[curq].r==i){
      ll val1=segans.get(1,1,n,q[curq].l,q[curq].r);
      ll val2=seg1.get(1,1,n,q[curq].l,q[curq].r);
      ll val3=seg2.get(1,1,n,q[curq].l,q[curq].r);
      ans[q[curq].id]=max(val1,max(val2,val3));
      curq++;
    }
    while(curen<=n&&en[curen].a==i){
      ll id=en[curen].id;
      seg1.update1(1,1,n,id,-INF);
      seg2.update1(1,1,n,id,-INF);
      curen++;
    }
  }
  for(i=1;i<=m;i++){
    if(ans[i]<0) cout<<-1<<'\n';
    else cout<<ans[i]<<'\n';
  }
  return 0;
}

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