Submission #3878535

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define chmax(a,b) a=max(a,b);
typedef long long ll;

using namespace std;
#define N 100010
#define D 20
class RMQxRMQ{
private:
    ll dat[2*N],laz[2*N];
    ll eval(ll k){
	if(k<N){
	    chmax(laz[k*2],laz[k]);
	    chmax(laz[k*2+1],laz[k]);
	}
	chmax(dat[k],laz[k]); laz[k]=-1;
	return dat[k];
    }
public:
    void Init(){
	lol(i,2*N)dat[i]=laz[i]=-1;
    }
    void Upd(ll l,ll r,ll x){
	l+=N,r+=N+1;
	for(ll a=l,b=r;a<b;a>>=1,b>>=1){
	    if(a&1){chmax(laz[a],x);a++;}
	    if(b&1){b--;chmax(laz[b],x);}
	}
	for(ll a=l,b=r;a+b;a>>=1,b>>=1){
	    dat[a/2]=max(eval(a),eval(a^1));
	    dat[b/2]=max(eval(b),eval(b^1));
	}
    }
    ll Qry(ll l,ll r){
	l+=N,r+=N+1;
	for(ll i=D;i;i--)eval(l>>i),eval(r>>i);
	ll res=0;
	for(ll a=l,b=r;a<b;a>>=1,b>>=1){
	    if(a&1)res=max(res,eval(a++));
	    if(b&1)res=max(res,eval(--b));
	}
	return res;
    }
};

ll s[N][D][2],n,k,q,a[N];
void MakeTree(ll ind){
    RMQxRMQ seg;seg.Init();
    lol(i,n){
	ll to=seg.Qry(a[i],N-2);
	if(!ind)s[i][0][0]=to;
	else s[n-1-i][0][1]=n-1-to;
	seg.Upd(a[i],a[i],i);
    }
    s[0][0][0]=s[0][0][1]=0;
    s[n-1][0][0]=s[n-1][0][1]=n-1;
}
ll $0(ll a,ll b,ll d){
    return min(s[a][d][0],s[b][d][0]);
}
ll $1(ll a,ll b,ll d){
    return max(s[a][d][1],s[b][d][1]);
}
void MakeTable(){
    for(ll d=0;d<D-1;d++)lol(i,n){
	ll a=s[i][d][0],b=s[i][d][1];
	s[i][d+1][0]=$0(a,b,d);
	s[i][d+1][1]=$1(a,b,d);
    }
}
void Solve(ll a,ll b){
    ll l=a,r=b,ans=0;
    a=b=r;
    for(ll d=D-2;~d;d--){
	ll v0=$0(a,b,d),v1=$1(a,b,d);
	if(v0<=l)continue;
	a=v0,b=v1,ans+=(1LL<<d);
    }
    r=a,a=b=l;
    for(ll d=D-2;~d;d--){
	ll v0=$0(a,b,d),v1=$1(a,b,d);
	if(v1>=r)continue;
	a=v0,b=v1,ans+=(1LL<<d);
    }
    printf("%lld\n",ans);
}
int main(){
    cin>>n>>k>>q;
    lol(i,n)scanf("%lld",&a[i+1]);
    n+=2,a[0]=a[n-1]=N-2;
    lol(r,2){
	MakeTree(r);
	lol(i,n/2)swap(a[i],a[n-i-1]);
    }
    MakeTable();
    lol(u,q){
	ll a,b;cin>>a>>b;
	Solve(min(a,b),max(a,b));
    }
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:94:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     lol(i,n)scanf("%lld",&a[i+1]);
                                  ^

Judge Result