Submission #3769066
Source Code Expand
#include <iostream> #include <algorithm> using namespace std; #define REP(i,n) for (int i = 0; i < n; i++) const int MAX = 1e5+10; int N, L, Q; int x[MAX]; int dp[MAX][22]; int main() { cin >> N; REP (i, N) cin >> x[i+1]; cin >> L >> Q; REP (i, 20) dp[N+1][i] = dp[N][i] = N+1; for (int i = N-1; i >= 1; i--) { int lo = i+1, hi = N+1; while (hi-lo > 1) { int mid = (hi+lo)/2; if (x[mid]-x[i] <= L) lo = mid; else hi = mid; } dp[i][0] = lo; for (int j = 1; j < 20; j++) { dp[i][j] = dp[ dp[i][j-1] ][j-1]; } } REP (q, Q) { int a, b; cin >> a >> b; if (a > b) swap(a, b); int ans = 0; for (int i = 19; i >= 0; i--) { if (dp[a][i] <= b) { ans += (1<<i); a = dp[a][i]; } } cout << ans << endl; } }
Submission Info
Submission Time | |
---|---|
Task | E - Tak and Hotels |
User | tnyo43 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 871 Byte |
Status | WA |
Exec Time | 359 ms |
Memory | 9856 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 200 | 0 / 500 | ||||||||||
Status |
|
|
|
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 | 1 ms | 256 KB |
subtask1_01.txt | WA | 1 ms | 256 KB |
subtask1_02.txt | AC | 1 ms | 256 KB |
subtask1_03.txt | WA | 4 ms | 384 KB |
subtask1_04.txt | AC | 4 ms | 384 KB |
subtask1_05.txt | WA | 4 ms | 384 KB |
subtask1_06.txt | AC | 3 ms | 256 KB |
subtask1_07.txt | WA | 3 ms | 256 KB |
subtask1_08.txt | WA | 4 ms | 384 KB |
subtask1_09.txt | WA | 4 ms | 384 KB |
subtask1_10.txt | WA | 4 ms | 384 KB |
subtask1_11.txt | WA | 4 ms | 384 KB |
subtask1_12.txt | WA | 4 ms | 384 KB |
subtask1_13.txt | WA | 4 ms | 384 KB |
subtask2_01.txt | WA | 333 ms | 9728 KB |
subtask2_02.txt | AC | 354 ms | 9728 KB |
subtask2_03.txt | WA | 355 ms | 9600 KB |
subtask2_04.txt | WA | 208 ms | 6784 KB |
subtask2_05.txt | WA | 220 ms | 6912 KB |
subtask2_06.txt | WA | 324 ms | 9472 KB |
subtask2_07.txt | WA | 334 ms | 9728 KB |
subtask2_08.txt | WA | 359 ms | 9728 KB |
subtask2_09.txt | WA | 345 ms | 9728 KB |
subtask2_10.txt | WA | 348 ms | 9728 KB |
subtask2_11.txt | WA | 337 ms | 9344 KB |
subtask2_12.txt | WA | 314 ms | 9856 KB |
subtask2_13.txt | WA | 308 ms | 9472 KB |