Submission #856647


Source Code Expand

Copy
//WA!
//http://arc060.contest.atcoder.jp/tasks/arc060_c
#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 && x[k]!=x[b]) ans++;
//    else 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
Task E - Tak and Hotels
User Agassaa
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1332 Byte
Status WA
Exec Time 1246 ms
Memory 40704 KB

Judge Result

Set Name Sample Subtask1 All
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
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 WA 4 ms 256 KB
subtask1_02.txt WA 4 ms 256 KB
subtask1_03.txt WA 13 ms 640 KB
subtask1_04.txt WA 15 ms 640 KB
subtask1_05.txt WA 17 ms 640 KB
subtask1_06.txt WA 12 ms 512 KB
subtask1_07.txt WA 8 ms 512 KB
subtask1_08.txt WA 15 ms 640 KB
subtask1_09.txt WA 13 ms 640 KB
subtask1_10.txt WA 13 ms 640 KB
subtask1_11.txt WA 13 ms 640 KB
subtask1_12.txt WA 13 ms 640 KB
subtask1_13.txt WA 14 ms 640 KB
subtask2_01.txt WA 1051 ms 40448 KB
subtask2_02.txt WA 1246 ms 40704 KB
subtask2_03.txt WA 1239 ms 40448 KB
subtask2_04.txt WA 639 ms 26496 KB
subtask2_05.txt WA 760 ms 26624 KB
subtask2_06.txt WA 1167 ms 40320 KB
subtask2_07.txt WA 1049 ms 40576 KB
subtask2_08.txt WA 1217 ms 40576 KB
subtask2_09.txt WA 1102 ms 40704 KB
subtask2_10.txt WA 1226 ms 40576 KB
subtask2_11.txt WA 1032 ms 37504 KB
subtask2_12.txt WA 987 ms 40704 KB
subtask2_13.txt WA 1033 ms 40320 KB