Contest Duration: - (local time) (100 minutes) Back to Home

Submission #855919

Source Code Expand

Copy
```#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(X,Y) ((X)>(Y)?X=(Y),true:false)
#define chmax(X,Y) ((X)<(Y)?X=(Y),true:false)
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}

#define N 100010
#define B 32

ll x[N], dp[B][N];
ll n, l, q;

int main(){
cin>>n;
rep(i, n) cin>>x[i];
cin>>l>>q;
x[n] = x[n-1]+l+1;
{
int lx = 0, rx = 0;
while(lx < n){
while(x[rx]-x[lx]<=l) rx++;
dp[0][lx] = rx-1;
lx++;
}
for(int i = 1; i < B; i++){
for(int j = 0; j < n; j++){
dp[i][j] = dp[i-1][dp[i-1][j]];
}
}
}
rep(_, q){
int a, b;
cin>>a>>b; a--; b--;
if(a>b) swap(a, b);
int lb = 0, ub = n-1; // (lb, ub]
while(ub-lb>1){
int md = (lb+ub+1)/2;
int s = a;
for(int j = 0; j < B; j++){
if(1&(md>>j)) s = dp[j][s];
}
(b<=s?ub:lb)=md;
}
cout<<ub<<endl;
}
return 0;
}
```

#### Submission Info

Submission Time 2016-08-28 21:39:13+0900 E - Tak and Hotels Lepton C++14 (GCC 5.4.1) 700 1843 Byte AC 1210 ms 26624 KB

#### Judge Result

Score / Max Score 0 / 0 200 / 200 500 / 500
Status
 AC × 1
 AC × 14
 AC × 27
Set Name Test Cases
Sample example_01.txt
Case Name Status Exec Time Memory
example_01.txt AC 4 ms 384 KB
subtask1_01.txt AC 5 ms 384 KB
subtask1_02.txt AC 4 ms 384 KB
subtask1_03.txt AC 13 ms 640 KB
subtask1_04.txt AC 13 ms 640 KB
subtask1_05.txt AC 13 ms 640 KB
subtask1_06.txt AC 9 ms 512 KB
subtask1_07.txt AC 8 ms 512 KB
subtask1_08.txt AC 13 ms 640 KB
subtask1_09.txt AC 14 ms 640 KB
subtask1_10.txt AC 13 ms 640 KB
subtask1_11.txt AC 13 ms 640 KB
subtask1_12.txt AC 14 ms 640 KB
subtask1_13.txt AC 13 ms 640 KB
subtask2_01.txt AC 1115 ms 26496 KB
subtask2_02.txt AC 1193 ms 26624 KB
subtask2_03.txt AC 1115 ms 26368 KB
subtask2_04.txt AC 651 ms 17408 KB
subtask2_05.txt AC 715 ms 17536 KB
subtask2_06.txt AC 988 ms 26240 KB
subtask2_07.txt AC 1187 ms 26496 KB
subtask2_08.txt AC 1196 ms 26624 KB
subtask2_09.txt AC 1194 ms 26624 KB
subtask2_10.txt AC 1210 ms 26624 KB
subtask2_11.txt AC 1210 ms 24704 KB
subtask2_12.txt AC 974 ms 26624 KB
subtask2_13.txt AC 976 ms 26240 KB