Submission #857755


Source Code Expand

Copy
//WA!
//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][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
Task E - Tak and Hotels
User Agassaa
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1764 Byte
Status WA
Exec Time 296 ms
Memory 40704 KB

Judge Result

Set Name Sample Subtask1 All
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
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 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