Submission #855695

---

Source Code Expand

// eddy1021
#include <bits/stdc++.h>
using namespace std;
typedef double D;
typedef long double LD;
typedef long long ll;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<LD,LD> Pt;
typedef tuple<int,int,int> tiii;
typedef tuple<LL,LL,LL> tlll;
#define mod9 1000000009ll
#define mod7 1000000007ll
#define INF  1023456789ll
#define INF16 10000000000000000ll
#define FI first
#define SE second
#define X FI
#define Y SE
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define eps 1e-9
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#ifndef ONLINE_JUDGE
#define debug(...) printf(__VA_ARGS__)
#else 
#define debug(...)
#endif
inline ll getint(){
  ll _x=0,_tmp=1; char _tc=getchar();    
  while( (_tc<'0'||_tc>'9')&&_tc!='-' ) _tc=getchar();
  if( _tc == '-' ) _tc=getchar() , _tmp = -1;
  while(_tc>='0'&&_tc<='9') _x*=10,_x+=(_tc-'0'),_tc=getchar();
  return _x*_tmp;
}
inline ll add( ll _x , ll _y , ll _mod = mod7 ){
  ll _ = _x + _y;
  if( _ >= _mod ) _ -= _mod;
  return _;
}
inline ll sub( ll _x , ll _y , ll _mod = mod7 ){
  ll _ = _x - _y;
  if( _ < 0 ) _ += _mod;
  return _;
}
inline ll mul( ll _x , ll _y , ll _mod = mod7 ){
  ll _ = _x * _y;
  if( _ >= _mod ) _ %= _mod;
  return _;
}
ll mypow( ll _a , ll _x , ll _mod ){
  if( _x == 0 ) return 1ll;
  ll _tmp = mypow( _a , _x / 2 , _mod );
  _tmp = mul( _tmp , _tmp , _mod );
  if( _x & 1 ) _tmp = mul( _tmp , _a , _mod );
  return _tmp;
}
ll mymul( ll _a , ll _x , ll _mod ){
  if( _x == 0 ) return 0ll;
  ll _tmp = mymul( _a , _x / 2 , _mod );
  _tmp = add( _tmp , _tmp , _mod );
  if( _x & 1 ) _tmp = add( _tmp , _a , _mod );
  return _tmp;
}
inline bool equal( D _x ,  D _y ){
  return _x > _y - eps && _x < _y + eps;
}
int __ = 1 , _cs;
/*********default*********/
#define N 202020
struct Seg{
  int vl , tag , lft , rgt;
  Seg(){
    vl = tag = lft = rgt = 0;
  }
} st[ N << 5 ];
int _cnt = 1;
int copy( int id ){
  int now = _cnt ++;
  st[ now ] = st[ id ];
  return now;
}
#define mid ((l+r)>>1)
void push( int now , int l , int r ){
  if( st[ now ].tag ){
    st[ now ].lft = copy( st[ now ].lft );
    st[ now ].rgt = copy( st[ now ].rgt );
    st[ st[ now ].lft ].vl += st[ now ].tag;
    st[ st[ now ].lft ].tag += st[ now ].tag;
    st[ st[ now ].rgt ].vl += st[ now ].tag;
    st[ st[ now ].rgt ].tag += st[ now ].tag;
  }
  st[ now ].tag = 0;
}
void modify( int now , int l , int r , int ql , int qr ){
  if( r < ql || l > qr || ql > qr ) return;
  if( ql <= l && r <= qr ){
    st[ now ].vl ++;
    st[ now ].tag ++;
    return;
  }
  push( now , l , r );
  st[ now ].lft = copy( st[ now ].lft );
  st[ now ].rgt = copy( st[ now ].rgt );
  modify( st[ now ].lft , l , mid , ql , qr );
  modify( st[ now ].rgt , mid + 1 , r , ql , qr );
}
int query( int now , int l , int r , int pos ){
  if( now == 0 ){
    assert( false );
    return 0;
  }
  if( l == r ) return st[ now ].vl;
  push( now , l , r );
  if( pos <= mid ) return query( st[ now ].lft , l , mid , pos );
  return query( st[ now ].rgt , mid + 1 , r , pos );
}
void build(){

}
int n , x[ N ] , l , q , ans[ N ];
vector< PII > v[ N ];
void init(){
  n = getint();
  for( int i = 1 ; i <= n ; i ++ )
    x[ i ] = getint();
  l = getint();
  q = getint();
  for( int i = 0 ; i < q ; i ++ ){
    int ai = getint();
    int bi = getint();
    if( ai > bi ) swap( ai , bi );
    v[ ai ].push_back( { bi , i } );
  }
}
int root[ N ];
void solve(){
  root[ n ] = copy( 0 );
  for( int i = n - 1 ; i >= 1 ; i -- ){
    int bl = i + 1 , br = n , til = i + 1;
    while( bl <= br ){
      int bmid = ( bl + br ) >> 1;
      if( x[ bmid ] - x[ i ] <= l )
        til = bmid, bl = bmid + 1;
      else br = bmid - 1;
    }
    root[ i ] = copy( root[ til ] );
    modify( root[ i ] , 1 , n , i + 1 , n );
    for( PII qry : v[ i ] )
      ans[ qry.SE ] = query( root[ i ] , 1 , n , qry.FI );
  }
  for( int i = 0 ; i < q ; i ++ )
    printf( "%d\n" , ans[ i ] );
}
int main(){
  build();
  //__ = getint();
  while( __ -- ){
    init();
    solve();
  }
}

Submission Info

Judge Result