Submission #3768723
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][i] = N; 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][1] = lo; for (int j = 2; 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; while (a < b) { for (int i = 1; i < 20; i++) { if (dp[a][i] < b) continue; if (dp[a][i] == b) { ans += 1<<(i-1); a = b; break; } ans += 1<<(i-2); a = dp[a][i-1]; break; } } 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 | 1010 Byte |
Status | WA |
Exec Time | 3155 ms |
Memory | 9728 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 | TLE | 3155 ms | 256 KB |
subtask1_02.txt | AC | 1 ms | 256 KB |
subtask1_03.txt | TLE | 3155 ms | 384 KB |
subtask1_04.txt | WA | 4 ms | 384 KB |
subtask1_05.txt | TLE | 3155 ms | 384 KB |
subtask1_06.txt | WA | 3 ms | 256 KB |
subtask1_07.txt | TLE | 3155 ms | 256 KB |
subtask1_08.txt | TLE | 3155 ms | 384 KB |
subtask1_09.txt | TLE | 3155 ms | 384 KB |
subtask1_10.txt | TLE | 3155 ms | 384 KB |
subtask1_11.txt | TLE | 3155 ms | 384 KB |
subtask1_12.txt | TLE | 3155 ms | 384 KB |
subtask1_13.txt | TLE | 3155 ms | 384 KB |
subtask2_01.txt | TLE | 3155 ms | 9216 KB |
subtask2_02.txt | WA | 325 ms | 9728 KB |
subtask2_03.txt | TLE | 3155 ms | 9216 KB |
subtask2_04.txt | TLE | 3155 ms | 6656 KB |
subtask2_05.txt | TLE | 3155 ms | 6656 KB |
subtask2_06.txt | TLE | 3155 ms | 9216 KB |
subtask2_07.txt | TLE | 3155 ms | 9216 KB |
subtask2_08.txt | TLE | 3155 ms | 9216 KB |
subtask2_09.txt | TLE | 3155 ms | 9216 KB |
subtask2_10.txt | TLE | 3155 ms | 9216 KB |
subtask2_11.txt | TLE | 3155 ms | 8832 KB |
subtask2_12.txt | TLE | 3155 ms | 9216 KB |
subtask2_13.txt | TLE | 3155 ms | 9216 KB |