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

Submission #857815

Source Code Expand

Copy
```//WA:
//1. corner case, e.g. jump[k][1]>b then jump[k][0]<b
//2. last node should not be nth, cause it will loop and accept in range, so make an extra node n+1

#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][35];
ll cost[100010][35];
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;

//    cout<<jump[2][0]<<"!\n";

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;
//            cout<<i<<' '<<j<<' '<<jump[i][j]<<' '<<jump[i][j-1]<<'.'<<'\n';
//            if(jump[2][0]==10) cout<<i<<' '<<j<<' '<<jump[i][j-1]<<"!\n";
//            if(j==0) cout<<"_____\n";
}
}

ll q;
//    cout<<jump[2][0]<<"!\n";
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
//3
//1 9
//2 8
//2 6

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

```

#### Submission Info

Submission Time 2016-08-29 01:10:28+0900 E - Tak and Hotels Agassaa C++14 (GCC 5.4.1) 700 3124 Byte AC 329 ms 56320 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 256 KB
subtask1_01.txt AC 4 ms 256 KB
subtask1_02.txt AC 4 ms 256 KB
subtask1_03.txt AC 5 ms 768 KB
subtask1_04.txt AC 5 ms 768 KB
subtask1_05.txt AC 5 ms 768 KB
subtask1_06.txt AC 5 ms 512 KB
subtask1_07.txt AC 5 ms 512 KB
subtask1_08.txt AC 5 ms 768 KB
subtask1_09.txt AC 5 ms 768 KB
subtask1_10.txt AC 5 ms 768 KB
subtask1_11.txt AC 5 ms 768 KB
subtask1_12.txt AC 5 ms 768 KB
subtask1_13.txt AC 5 ms 768 KB
subtask2_01.txt AC 299 ms 56192 KB
subtask2_02.txt AC 329 ms 56320 KB
subtask2_03.txt AC 297 ms 56064 KB
subtask2_04.txt AC 147 ms 36736 KB
subtask2_05.txt AC 166 ms 36864 KB
subtask2_06.txt AC 245 ms 55936 KB
subtask2_07.txt AC 286 ms 56192 KB
subtask2_08.txt AC 309 ms 56320 KB
subtask2_09.txt AC 312 ms 56320 KB
subtask2_10.txt AC 322 ms 56320 KB
subtask2_11.txt AC 302 ms 51840 KB
subtask2_12.txt AC 231 ms 56320 KB
subtask2_13.txt AC 246 ms 55936 KB