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

Submission #856556

Source Code Expand

Copy
```#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll x[100010];
ll jump[100010][25];
ll cost[100010][25];
map<ll,ll> mp;

ll Find(ll a,ll b)
{
ll i,j,k,l;
ll ans=0;
k=a;
for(i=25;i>=0;i--)
{
l=jump[k][i];
//        cout<<k<<' '<<l<<' '<<i<<'\n';
if(l>b) continue;
//        ans+=i;
ans+=cost[k][i];
k=l;
//        cout<<'.';
}

if(k<b) ans++;
return ans;
}

int main()
{
ll i,j,k,l;
ll n,m,L,a,b;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>x[i];
}

cin>>L;
x[n+1]=10000000000;
j=1;
for(i=1;i<=n;i++)
{
while(x[j]-x[i]<=L) j++;
jump[i][0]=j-1;
cost[i][0]=1;
//        cout<<i<<' '<<j-1<<'\n';
}

for(j=1;j<=25;j++)
{
for(i=1;i<=n;i++)
{
jump[i][j]=jump[jump[i][j-1]][j-1];
cost[i][j]=cost[i][j-1]*2;
}
}

ll q;
cin>>q;
while(q--){
cin>>a>>b;
if(a>b) swap(a,b);
cout<<Find(a,b)<<'\n';
}
}

//9
//1 3 6 13 15 18 19 29 31
//10
//4
//1 8
//7 3
//6 7
//8 5

//9
//1 3 6 13 15 18 19 29 31
//10
//1 8
```

#### Submission Info

Submission Time 2016-08-28 22:10:12+0900 E - Tak and Hotels Agassaa C++14 (GCC 5.4.1) 0 1233 Byte WA 1160 ms 40704 KB

#### Judge Result

Score / Max Score 0 / 0 0 / 200 0 / 500
Status
 AC × 1
 AC × 1 WA × 13
 AC × 1 WA × 26
Set Name Test Cases
Sample example_01.txt
Case Name Status Exec Time Memory
example_01.txt AC 4 ms 256 KB
subtask1_01.txt WA 5 ms 256 KB
subtask1_02.txt WA 4 ms 256 KB
subtask1_03.txt WA 12 ms 640 KB
subtask1_04.txt WA 15 ms 640 KB
subtask1_05.txt WA 13 ms 640 KB
subtask1_06.txt WA 10 ms 512 KB
subtask1_07.txt WA 8 ms 512 KB
subtask1_08.txt WA 13 ms 640 KB
subtask1_09.txt WA 14 ms 640 KB
subtask1_10.txt WA 14 ms 640 KB
subtask1_11.txt WA 13 ms 640 KB
subtask1_12.txt WA 14 ms 640 KB
subtask1_13.txt WA 12 ms 640 KB
subtask2_01.txt WA 1047 ms 40448 KB
subtask2_02.txt WA 1121 ms 40704 KB
subtask2_03.txt WA 1095 ms 40448 KB
subtask2_04.txt WA 735 ms 26496 KB
subtask2_05.txt WA 665 ms 26624 KB
subtask2_06.txt WA 993 ms 40320 KB
subtask2_07.txt WA 1160 ms 40576 KB
subtask2_08.txt WA 1121 ms 40704 KB
subtask2_09.txt WA 1063 ms 40576 KB
subtask2_10.txt WA 1123 ms 40576 KB
subtask2_11.txt WA 1077 ms 37504 KB
subtask2_12.txt WA 1122 ms 40704 KB
subtask2_13.txt WA 1084 ms 40320 KB