Submission #120162

#	Time	Username	Problem	Language	Result	Execution time	Memory
120162		KLPP	Two Antennas (JOI19_antennas)	C++14	35 / 100	3026 ms	43664 KiB

antennas

#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 answer[3000][3000];
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 Min(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]);
  }
  if(n<=2000){
    ST *S=new ST();
    rep(i,1,n+1){
      S->build(1,n,1);
      vector<pii> v;
      rep(j,i,n+1){
	v.push_back(pii(j+a[j-1],j));
	v.push_back(pii(j+b[j-1]+1,-j));
      }
      sort(v.begin(),v.end());
      int ptr=0;
      lld ans=-1;
      //cout<<i<<endl;
      rep(j,i,n+1){
	while(ptr<v.size() && v[ptr].first<=j){
	  //cout<<"U"<<v[ptr].second<<" "<<v[ptr].first<<endl;
	  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,j-b[j-1],j-a[j-1]);
	M=S->QMax(1,n,1,j-b[j-1],j-a[j-1]);
	//cout<<m<<" "<<M<<endl;
	if(m!=-1)ans=max(ans,h[j-1]-m);
	if(M!=-1)ans=max(ans,M-h[j-1]);
	answer[i][j]=ans;
	//cout<<"A"<<answer[i][j]<<" "<<i<<" "<<j<<endl;
      }
    }
    int q;
    scanf("%d",&q);
    while(q--){
      //cout<<"A"<<endl;
      int l,r;
      scanf("%d %d",&l,&r);
      printf("%lld\n",answer[l][r]);
    }
    return 0;
  }
  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:80:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ptr<v.size() && v[ptr].first<=j){
        ~~~^~~~~~~~~
antennas.cpp:127: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:102:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
antennas.cpp:106:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d",&l,&r);
       ~~~~~^~~~~~~~~~~~~~~
antennas.cpp:113:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&q);
   ~~~~~^~~~~~~~~
antennas.cpp:116:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&l,&r);
     ~~~~~^~~~~~~~~~~~~~~

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