Submission #858869


Source Code Expand

Copy
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 200003;

int n , L , a[MAXN] , q , mx , ans , l , r;
int dp[MAXN][19];//dp[i][j]表示从第i个点跳2^j次,最多能跳到的点的下标

void solve() {
    a[n+1] = 0x3f3f3f3f;
    for(int i = 1 ; i <= n ; ++i) {//二分找到第i个点跳一次最远能到达的点的下标
        dp[i][0] = lower_bound(a + 1 , a + n + 2 , a[i] + L +1) - a - 1;
    }
    for(mx = 1 ; (1 << mx) <= n ; ++mx) {//更新dp[i][j]
        for(int i = 1 ; i <= n ; ++i) {
            dp[i][mx] = dp[dp[i][mx-1]][mx-1];
        }
    }
    --mx;
    scanf("%d" , &q);
    while(q-- >0) {
        scanf("%d%d" , &l , &r);
        if(l > r) {
            swap(l , r);
        }
        ans = 0;
        for(int i = mx ; i >=0 ;--i) {//从权重最大的开始枚举
            if(dp[l][i] < r) {
                ans += 1 << i;
                l = dp[l][i];
            }
        }
        while(l < r) {
            ++ans;
            l = dp[l][0];
        }
        printf("%d\n",ans);
    }
}

int main() {
    while(1 == scanf("%d", &n)) {
        for(int i = 1 ; i <= n ; ++i) {
            scanf("%d" , a+i);
        }
        scanf("%d" , &L);
        solve();
    }
    return 0;
}

Submission Info

Submission Time
Task E - Tak and Hotels
User idealism
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1325 Byte
Status TLE
Exec Time 3156 ms
Memory 8576 KB

Compile Error

./Main.cpp: In function ‘void solve()’:
./Main.cpp:23:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d" , &q);
                     ^
./Main.cpp:25:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d" , &l , &r);
                                ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:47:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d" , a+i);
                              ^
./Main.cpp:49:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d" , &L);
                         ^

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 200 0 / 500
Status
AC × 1
AC × 11
TLE × 3
AC × 21
TLE × 6
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 128 KB
subtask1_01.txt AC 2 ms 128 KB
subtask1_02.txt AC 2 ms 128 KB
subtask1_03.txt AC 3 ms 256 KB
subtask1_04.txt AC 3 ms 256 KB
subtask1_05.txt TLE 3153 ms 256 KB
subtask1_06.txt AC 3 ms 256 KB
subtask1_07.txt TLE 3156 ms 256 KB
subtask1_08.txt TLE 3153 ms 256 KB
subtask1_09.txt AC 3 ms 256 KB
subtask1_10.txt AC 3 ms 256 KB
subtask1_11.txt AC 3 ms 256 KB
subtask1_12.txt AC 3 ms 256 KB
subtask1_13.txt AC 3 ms 256 KB
subtask2_01.txt AC 132 ms 8448 KB
subtask2_02.txt AC 142 ms 8576 KB
subtask2_03.txt AC 127 ms 8320 KB
subtask2_04.txt TLE 3154 ms 5248 KB
subtask2_05.txt AC 84 ms 5632 KB
subtask2_06.txt TLE 3154 ms 7936 KB
subtask2_07.txt AC 131 ms 8448 KB
subtask2_08.txt AC 139 ms 8576 KB
subtask2_09.txt AC 138 ms 8576 KB
subtask2_10.txt AC 139 ms 8576 KB
subtask2_11.txt AC 134 ms 7936 KB
subtask2_12.txt AC 102 ms 8576 KB
subtask2_13.txt TLE 3154 ms 7936 KB