Submission #3774336


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define INF 1000000009
#define pb push_back

int N, L, Q, x[100005];
vector<int> G[100005], X;
map<int, int> mp;
int d[100005];

signed main()
{
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> x[i];
        mp[x[i]] = i;
        X.pb(-x[i]);
        d[i] = INF;
        if(i < N - 1){
            G[i].pb(i + 1);
        }
    }
    sort(X.begin(), X.end());
    cin >> L;
    for(int i = 0; i < N; i++){
        G[i].pb(mp[-*lower_bound(X.begin(), X.end(), -x[i] - L)]);
    }
    queue<int> que;
    que.push(0);
    d[0] = 0;
    while(!que.empty()){
        int v = que.front();
        que.pop();
        for(int i = 0; i < (int)G[v].size(); i++){
            int to = G[v][i];
            if(d[to] == INF){
                que.push(to);
                d[to] = d[v] + 1;
            }
        }
    }
    /*for(int i = 0; i < N; i++){
        for(int j = 0; j < (int)G[i].size(); j++){
            printf("G[%d][%d]:%d\n", i, j, G[i][j]);
        }
    }*/
    for(int i = N - 2; i >= 0; i--){
        if(d[i + 1] < d[i]){
            d[i] = d[i + 1];
        }
    }
    cin >> Q;
    for(int i = 0; i < Q; i++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        if(a < b)swap(a, b);
        cout << max(d[a] - d[b], 1) << endl;
    }

    return 0;
}

Submission Info

Submission Time
Task E - Tak and Hotels
User youluoy
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1405 Byte
Status WA
Exec Time 309 ms
Memory 12152 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 2 ms 2560 KB
subtask1_01.txt WA 3 ms 2560 KB
subtask1_02.txt AC 2 ms 2560 KB
subtask1_03.txt WA 5 ms 2688 KB
subtask1_04.txt AC 5 ms 2688 KB
subtask1_05.txt WA 5 ms 2688 KB
subtask1_06.txt AC 4 ms 2688 KB
subtask1_07.txt WA 4 ms 2688 KB
subtask1_08.txt AC 5 ms 2688 KB
subtask1_09.txt WA 5 ms 2688 KB
subtask1_10.txt WA 5 ms 2688 KB
subtask1_11.txt WA 5 ms 2688 KB
subtask1_12.txt WA 5 ms 2688 KB
subtask1_13.txt WA 5 ms 2688 KB
subtask2_01.txt WA 301 ms 12024 KB
subtask2_02.txt AC 304 ms 12152 KB
subtask2_03.txt WA 309 ms 11896 KB
subtask2_04.txt AC 201 ms 8572 KB
subtask2_05.txt WA 196 ms 8828 KB
subtask2_06.txt AC 308 ms 11768 KB
subtask2_07.txt WA 304 ms 12024 KB
subtask2_08.txt WA 301 ms 12152 KB
subtask2_09.txt WA 300 ms 12152 KB
subtask2_10.txt WA 308 ms 12152 KB
subtask2_11.txt WA 301 ms 11384 KB
subtask2_12.txt WA 298 ms 12152 KB
subtask2_13.txt WA 302 ms 11768 KB