Contest Duration: - (local time) (100 minutes) Back to Home

Submission #858896

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] = 0x7f7f7f7f;
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 2016-08-29 17:37:40+0900 E - Tak and Hotels idealism C++14 (GCC 5.4.1) 700 1327 Byte AC 149 ms 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 200 / 200 500 / 500
Status
 AC × 1
 AC × 14
 AC × 27
Set Name Test Cases
Sample example_01.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 AC 3 ms 256 KB
subtask1_06.txt AC 3 ms 256 KB
subtask1_07.txt AC 3 ms 256 KB
subtask1_08.txt AC 3 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 133 ms 8448 KB
subtask2_02.txt AC 149 ms 8576 KB
subtask2_03.txt AC 130 ms 8320 KB
subtask2_04.txt AC 69 ms 5376 KB
subtask2_05.txt AC 91 ms 5632 KB
subtask2_06.txt AC 103 ms 8192 KB
subtask2_07.txt AC 135 ms 8448 KB
subtask2_08.txt AC 144 ms 8576 KB
subtask2_09.txt AC 142 ms 8576 KB
subtask2_10.txt AC 143 ms 8576 KB
subtask2_11.txt AC 138 ms 7936 KB
subtask2_12.txt AC 105 ms 8576 KB
subtask2_13.txt AC 101 ms 8192 KB