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

//http://arc060.contest.atcoder.jp/tasks/arc060_c

#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
//answer
//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
Task E - Tak and Hotels
User Agassaa
Language C++14 (GCC 5.4.1)
Score 700
Code Size 3124 Byte
Status AC
Exec Time 329 ms
Memory 56320 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 200 / 200 500 / 500
Status
AC × 1
AC × 14
AC × 27
Set Name Test Cases
Sample example_01.txt
Subtask1 example_01.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt
All example_01.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.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