Submission #858919


Source Code Expand

Copy
    #include <cstdlib>
    #include <cmath>
    #include <climits>
    #include <cfloat>
    #include <map>
    #include <utility>
    #include <set>
    #include <iostream>
    #include <memory>
    #include <string>
    #include <vector>
    #include <algorithm>
    #include <functional>
    #include <sstream>
    #include <deque>
    #include <complex>
    #include <stack>
    #include <queue>
    #include <cstdio>
    #include <cctype>
    #include <cstring>
    #include <ctime>
    #include <iterator>
    #include <bitset>
    #include <numeric>
    #include <list>
    #include <iomanip>
    #include <cassert>
    #include <array>
    #include <tuple>
    #include <initializer_list>
    #include <unordered_set>
    #include <unordered_map>
    #include <forward_list>
    using namespace std;
    using ll = long long;
    #define rep(j,k) for (int j = 0; j < (int)(k); j++)
     
    int n;
    ll x[100010];
    ll L;
    int Q;
    int a[100010], b[100010];
     
    const int LOG = 20;
    ll go[100010][LOG];
     
    int f(int a, int x) {
        for (int i = 0; x; ++i, x /= 2) {
            if (x & 1) a = go[a][i];
        }
        return a;
    }
     
    int main() {
        ios::sync_with_stdio(0);
        cin.tie(0);
     
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> x[i];
        }
        x[n] = 2e9;
        cin >> L >> Q;
        for (int i = 0; i < n; i++) {
            int k = upper_bound(x + i, x + n, x[i] + L) - x;
            go[i][0] = k - 1;
        }
        for (int i = 0; i < LOG - 1; i++) {
            for (int j = 0; j < n; j++) {
                go[j][i + 1] = go[go[j][i]][i];
            }
        }
        for (int i = 0; i < Q; i++) {
            int a, b;
            cin >> a >> b;
            --a; --b;
            if (a > b) swap(a, b);
            int lb = 0, ub = n;
            while (lb + 1 < ub) {
                int mid = (lb + ub) / 2;
                if (f(a, mid) >= b) ub = mid;
                else lb = mid;
            }
            cout << ub << endl;
        }
    }

Submission Info

Submission Time
Task E - Tak and Hotels
User tubo28
Language C++14 (GCC 5.4.1)
Score 700
Code Size 2163 Byte
Status AC
Exec Time 1222 ms
Memory 17280 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 11 ms 384 KB
subtask1_04.txt AC 13 ms 384 KB
subtask1_05.txt AC 11 ms 384 KB
subtask1_06.txt AC 8 ms 384 KB
subtask1_07.txt AC 8 ms 384 KB
subtask1_08.txt AC 11 ms 384 KB
subtask1_09.txt AC 11 ms 384 KB
subtask1_10.txt AC 11 ms 384 KB
subtask1_11.txt AC 11 ms 384 KB
subtask1_12.txt AC 11 ms 384 KB
subtask1_13.txt AC 11 ms 384 KB
subtask2_01.txt AC 1053 ms 17152 KB
subtask2_02.txt AC 1222 ms 17280 KB
subtask2_03.txt AC 945 ms 17024 KB
subtask2_04.txt AC 557 ms 11136 KB
subtask2_05.txt AC 534 ms 11264 KB
subtask2_06.txt AC 729 ms 16896 KB
subtask2_07.txt AC 966 ms 17152 KB
subtask2_08.txt AC 986 ms 17280 KB
subtask2_09.txt AC 1074 ms 17280 KB
subtask2_10.txt AC 1050 ms 17280 KB
subtask2_11.txt AC 1003 ms 15872 KB
subtask2_12.txt AC 889 ms 17280 KB
subtask2_13.txt AC 734 ms 16896 KB