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

Submission #857755

Source Code Expand

Copy
```//WA!

#define IOS ios_base::sync_with_stdio(false);\
cin.tie(NULL);cout.tie(NULL);
#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<<ans<<'.'<<'\n';
}

if(k<b && x[k]!=x[b]) ans++;
//    else if(k<b) ans++;
//    cout<<ans<<"#\n";
return ans;
}

int main()
{
IOS;
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';
}

//special case
jump[n][0]=n+1;
cost[n][0]=x[n+1];
jump[n+1][0]=n+1;
cost[n+1][0]=x[n+1];
int WA=1;

for(j=1;j<=25;j++)
{
for(i=1;i<=n+WA;i++)
{
jump[i][j]=jump[jump[i][j-1]][j-1];
cost[i][j]=cost[i][j-1]*2; //wa, overcounting cost[n][j].
//            if(jump[i][j-1] < jump[i][j]) 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
//1 8

//WA:
//9
//1 3 6 13 15 18 19 29 31
//10
//1
//1 9

```

#### Submission Info

Submission Time 2016-08-29 00:38:19+0900 E - Tak and Hotels Agassaa C++14 (GCC 5.4.1) 0 1764 Byte WA 296 ms 40704 KB

#### Judge Result

Score / Max Score 0 / 0 0 / 200 0 / 500
Status
 AC × 1
 AC × 5 WA × 9
 AC × 8 WA × 19
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 4 ms 256 KB
subtask1_02.txt AC 4 ms 256 KB
subtask1_03.txt WA 6 ms 640 KB
subtask1_04.txt AC 6 ms 640 KB
subtask1_05.txt WA 6 ms 640 KB
subtask1_06.txt AC 5 ms 512 KB
subtask1_07.txt WA 5 ms 512 KB
subtask1_08.txt AC 6 ms 640 KB
subtask1_09.txt WA 6 ms 640 KB
subtask1_10.txt WA 6 ms 640 KB
subtask1_11.txt WA 6 ms 640 KB
subtask1_12.txt WA 6 ms 640 KB
subtask1_13.txt WA 6 ms 640 KB
subtask2_01.txt WA 277 ms 40576 KB
subtask2_02.txt AC 296 ms 40704 KB
subtask2_03.txt WA 269 ms 40448 KB
subtask2_04.txt AC 127 ms 26496 KB
subtask2_05.txt WA 145 ms 26624 KB
subtask2_06.txt AC 224 ms 40320 KB
subtask2_07.txt WA 256 ms 40576 KB
subtask2_08.txt WA 284 ms 40704 KB
subtask2_09.txt WA 282 ms 40704 KB
subtask2_10.txt WA 282 ms 40704 KB
subtask2_11.txt WA 267 ms 37504 KB
subtask2_12.txt WA 215 ms 40704 KB
subtask2_13.txt WA 227 ms 40320 KB