Submission #137389

#	Time	Username	Problem	Language	Result	Execution time	Memory
137389		KLPP	Triple Jump (JOI19_jumps)	C++14	100 / 100	3384 ms	227452 KiB

jumps

#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
class ST{
  lld tree[4000000];
public:
  void build(int a, int b, int node){
    if(a==b){
      tree[node]=0;
      return;
    }
    int mid=(a+b)/2;
    build(a,mid,2*node);
    build(mid+1,b,2*node+1);
    tree[node]=max(tree[node*2],tree[node*2+1]);
  }
  void update(int a, int b, int node, int pos, lld val){
    if(pos<a || b<pos)return;
    if(a==b){
      tree[node]=val;
      return;
    }
    int mid=(a+b)/2;
    update(a,mid,2*node,pos,val);
    update(mid+1,b,2*node+1,pos,val);
    tree[node]=max(tree[node*2],tree[node*2+1]);
  }
  lld query(int a, int b, int node, int x, int y){
    if(x>y)return -100000000000;
    if(b<x || y<a)return -100000000000;
    if(x<=a && b<=y)return tree[node];
    int mid=(a+b)/2;
    return max(query(a,mid,2*node,x,y),query(mid+1,b,2*node+1,x,y));
  }
};
class ST2{
  lld tree[4000000];
  lld lazy[4000000];
  lld Historic[4000000];
  lld Historic_lazy[1000000];
public:
  void build(int a, int b, int node){
    Historic_lazy[node]=0;
    lazy[node]=0;
    if(a==b){
      tree[node]=0;
      Historic[node]=0;
      return;
    }
    int mid=(a+b)/2;
    build(a,mid,2*node);
    build(mid+1,b,2*node+1);
    tree[node]=max(tree[2*node],tree[2*node+1]);
    Historic[node]=0;
    Historic[node]=max(Historic[node],tree[node]);
  }
  void propagate(int a, int b, int node){
    
    Historic[node]=max(Historic[node],tree[node]+Historic_lazy[node]);
    tree[node]+=lazy[node];
    if(a!=b){
      
      Historic_lazy[2*node]=max(Historic_lazy[2*node],lazy[2*node]+Historic_lazy[node]);
      lazy[2*node]+=lazy[node];
      
      Historic_lazy[2*node+1]=max(Historic_lazy[2*node+1],lazy[2*node+1]+Historic_lazy[node]);
      lazy[2*node+1]+=lazy[node];
    }
    lazy[node]=0;
    Historic_lazy[node]=0;
  }
  void update(int a, int b, int node,int x, int y, lld val){
    propagate(a,b,node);
    if(y<a || b<x)return;
    if(x<=a && b<=y){
      lazy[node]+=val;
      Historic_lazy[node]=max(lazy[node],Historic_lazy[node]);
      propagate(a,b,node);
      return;
    }
    int mid=(a+b)/2;
    update(a,mid,2*node,x,y,val);
    update(mid+1,b,2*node+1,x,y,val);
    tree[node]=max(tree[2*node],tree[2*node+1]);
    Historic[node]=max(Historic[2*node],Historic[2*node+1]);
  }
  lld query(int a, int b, int node, int x, int y){
    propagate(a,b,node);
   
    if(y<a || b<x)return -1000000000;
    if(x<=a && b<=y)return Historic[node];
    int mid=(a+b)/2;
    return max(query(a,mid,2*node,x,y),query(mid+1,b,2*node+1,x,y));
  }
  void print(int a, int b, int node){
    cout<<a<<" "<<b<<" "<<tree[node]<<" "<<Historic[node]<<" "<<lazy[node]<<" "<<Historic_lazy[node]<<endl;
    if(a==b)return;
    int mid=(a+b)/2;
    print(a,mid,2*node);
    print(mid+1,b,2*node+1);
  }
};
int main(){
  srand(time(NULL));
  int n,q;
  scanf("%d",&n);
  lld arr[n];
  rep(i,0,n){

    scanf("%lld",&arr[i]);
    //arr[i]=rand()%100;
  }
  scanf("%d",&q);
  vector<pair<int,int> > Queries[n];
  rep(i,0,q){
    int l,r;
    scanf("%d %d",&l,&r);
    l--;r--;
    Queries[l].push_back(pair<int,int>(r,i));
  }
  ST *S=new ST();
  S->build(0,n-1,1);
  rep(i,0,n)S->update(0,n-1,1,i,arr[i]);
  set<int> candidates;
  vector<int> V[n];
  for(int i=n-1;i>-1;i--){
    queue<int> eliminate;
    for(set<int>::iterator it=candidates.begin();it!=candidates.end();it++){
      //cout<<a<<" "<<i<<" "<<S->query(0,n-1,1,i+1,a-1)<<endl;
      int a=*it;
      if(S->query(0,n-1,1,i+1,a-1)<min(arr[i],arr[a])){
	V[i].push_back(a);
      }
      if(S->query(0,n-1,1,i+1,a-1)>arr[i]){
	it=candidates.end();
	it--;
      }
      if(S->query(0,n-1,1,i+1,a-1)>arr[a]){
	eliminate.push(a);
      }
    }
    while(!eliminate.empty()){
      candidates.erase(eliminate.front());
      eliminate.pop();
    }
    /*trav(a,candidates){
      //cout<<a<<" "<<i<<" "<<S->query(0,n-1,1,i+1,a-1)<<endl;
      if(S->query(0,n-1,1,i+1,a-1)>=arr[a]){
	candidates.erase(a);
      }
    }*/
    
    //candidates.erase(candidates.begin(),candidates.upper_bound(arr[i]));
    candidates.insert(i);
    
  }
  ST2 *Tree=new ST2();
  Tree->build(0,n-1,1);
  rep(i,0,n){
    Tree->update(0,n-1,1,i,i,arr[i]);
  }
  //Tree->print(0,n-1,1);
  lld answers[q];
  for(int i=n-1;i>-1;i--){
    trav(a,V[i]){
      if(2*a-i<=n-1){
	//cout<<i<<" "<<a<<endl;
	Tree->update(0,n-1,1,2*a-i,n-1,arr[i]+arr[a]);
	//Tree->print(0,n-1,1);
	//cout<<endl;
	Tree->update(0,n-1,1,2*a-i,n-1,-(arr[i]+arr[a]));
	//Tree->print(0,n-1,1);
	//cout<<endl;
      }
    }
    trav(a,Queries[i]){
      answers[a.second]=Tree->query(0,n-1,1,i,a.first);
    }
  }
  rep(i,0,q){
    printf("%lld\n",answers[i]);
  }
  /*lld ans2=0;
  rep(i,0,n){
    rep(j,i+1,n){
      rep(k,2*j-i,n){
	ans2=max(ans2,arr[i]+arr[j]+arr[k]);
      }
    }
  }
  rep(i,0,n){
    rep(j,i+1,n){
      rep(k,2*j-i,n){
	if(arr[i]+arr[j]+arr[k]==ans2)cout<<i<<" "<<j<<" "<<k<<endl;
      }
    }
  }
  cout<<ans2<<endl;
  if(ans!=ans2){
    rep(i,0,n)cout<<arr[i]<<" ";
    cout<<endl;
  }*/
  return 0;
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
jumps.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&arr[i]);
     ~~~~~^~~~~~~~~~~~~~~~
jumps.cpp:116:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&q);
   ~~~~~^~~~~~~~~
jumps.cpp:120: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: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54