Submission #120146

#TimeUsernameProblemLanguageResultExecution timeMemory
120146KLPPTwo Antennas (JOI19_antennas)C++14
0 / 100
298 ms32612 KiB
#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
typedef pair<lld,lld> pii;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
int n;
lld h[1000000];
lld a[1000000];
lld b[1000000];

lld Max(lld a, lld b){
  if(a==-1)return b;
  if(b==-1)return a;
  return max(a,b);
}
lld Min(lld a, lld b){
  if(a==-1)return b;
  if(b==-1)return a;
  return min(a,b);
}
class ST{
  lld tree1[1000000];
  lld tree2[1000000];
public:
  void build(int a, int b, int node){
    tree1[node]=-1;
    tree2[node]=-1;
    if(a==b)return;
    int mid=(a+b)/2;
    build(a,mid,2*node);
    build(mid+1,b,2*node+1);
  }
  void update(int a, int b, int node, int pos, lld val){
    if(pos<a || b<pos)return;
    if(a==b){
      tree1[node]=val;
      tree2[node]=val;
      return;
    }
    int mid=(a+b)/2;
    update(a,mid,2*node,pos,val);
    update(mid+1,b,2*node+1,pos,val);
    tree1[node]=Max(tree1[2*node],tree1[2*node+1]);
    tree2[node]=Min(tree2[2*node],tree2[2*node+1]);
  }
  lld QMax(int a, int b, int node, int x, int y){
    if(b<x || y<a)return -1;
    if(x<=a && b<=y)return tree1[node];
    int mid=(a+b)/2;
    return Max(QMax(a,mid,2*node,x,y),QMax(mid+1,b,2*node+1,x,y));
  }
  lld QMin(int a, int b, int node, int x, int y){
    if(b<x || y<a)return -1;
    if(x<=a && b<=y)return tree2[node];
    int mid=(a+b)/2;
    return Max(QMin(a,mid,2*node,x,y),QMin(mid+1,b,2*node+1,x,y));
  }
};
int main(){
  scanf("%d",&n);
  rep(i,0,n){
    scanf("%lld %lld %lld",&h[i],&a[i],&b[i]);
  }
  ST *S=new ST();
  int q;
  scanf("%d",&q);
  while(q--){
    int l,r;
    scanf("%d %d",&l,&r);
    S->build(1,n,1);
    vector<pii> v;
    rep(i,l,r+1){
      v.push_back(pii(i+a[i-1],i));
      v.push_back(pii(i+b[i-1]+1,-i));
    }
    sort(v.begin(),v.end());
    int ptr=0;
    lld ans=-1;
    rep(i,l,r+1){
      while(ptr<v.size() && v[ptr].first<=i){
	if(v[ptr].second>0){
	  S->update(1,n,1,v[ptr].second,h[v[ptr].second-1]);
	}else{
	  S->update(1,n,1,-v[ptr].second,-1);
	}
	ptr++;
      }
      lld m,M;
      
      
      m=S->QMin(1,n,1,i-b[i-1],i-a[i-1]);
      M=S->QMax(1,n,1,i-b[i-1],i-a[i-1]);
      //cout<<m<<" "<<M<<endl;
      if(m!=-1)ans=max(ans,h[i-1]-m);
      if(M!=-1)ans=max(ans,M-h[i-1]);
    }
    printf("%lld\n",ans);
  }
  return 0;
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:82:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while(ptr<v.size() && v[ptr].first<=i){
             ~~~^~~~~~~~~
antennas.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
antennas.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld %lld",&h[i],&a[i],&b[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&q);
   ~~~~~^~~~~~~~~
antennas.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&l,&r);
     ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...