Submission #3385744
Source Code Expand
#include<bits/stdc++.h> #define N 100010 using namespace std; template<typename T>inline void read(T &x) { x=0; static int p;p=1; static char c;c=getchar(); while(!isdigit(c)){if(c=='-')p=-1;c=getchar();} while(isdigit(c)) {x=(x<<1)+(x<<3)+(c-'0');c=getchar();} x*=p; } int n; int h[N],l,q; int st[N][19]; int main() { read(n); for(int i=1;i<=n;i++) read(h[i]); read(l);read(q); for(int i=1;i<=n;i++) { int pos=upper_bound(h+1,h+n+1,h[i]+l)-h-1; if(h[i]+l>=h[n])st[i][0]=n; else st[i][0]=pos; } for(int len=1;len<=18;len++) for(int i=1;i<=n;i++) st[i][len]=st[st[i][len-1]][len-1]; while(q--) { static int a,b; read(a);read(b); if(a>b)swap(a,b); int now=a,ans=0; for(int i=18;i>=0;i--) if(st[now][i]<b)now=st[now][i],ans+=(1<<i); printf("%d\n",ans+1); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Tak and Hotels |
User | pengym |
Language | C++ (GCC 5.4.1) |
Score | 700 |
Code Size | 805 Byte |
Status | AC |
Exec Time | 63 ms |
Memory | 8704 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 200 | 500 / 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 | AC | 1 ms | 256 KB |
subtask1_02.txt | AC | 1 ms | 256 KB |
subtask1_03.txt | AC | 1 ms | 384 KB |
subtask1_04.txt | AC | 2 ms | 384 KB |
subtask1_05.txt | AC | 1 ms | 384 KB |
subtask1_06.txt | AC | 1 ms | 256 KB |
subtask1_07.txt | AC | 1 ms | 256 KB |
subtask1_08.txt | AC | 1 ms | 384 KB |
subtask1_09.txt | AC | 2 ms | 384 KB |
subtask1_10.txt | AC | 2 ms | 384 KB |
subtask1_11.txt | AC | 2 ms | 384 KB |
subtask1_12.txt | AC | 2 ms | 384 KB |
subtask1_13.txt | AC | 2 ms | 384 KB |
subtask2_01.txt | AC | 56 ms | 8448 KB |
subtask2_02.txt | AC | 63 ms | 8576 KB |
subtask2_03.txt | AC | 55 ms | 8448 KB |
subtask2_04.txt | AC | 27 ms | 6784 KB |
subtask2_05.txt | AC | 36 ms | 6912 KB |
subtask2_06.txt | AC | 41 ms | 8192 KB |
subtask2_07.txt | AC | 57 ms | 8576 KB |
subtask2_08.txt | AC | 61 ms | 8576 KB |
subtask2_09.txt | AC | 61 ms | 8576 KB |
subtask2_10.txt | AC | 61 ms | 8576 KB |
subtask2_11.txt | AC | 60 ms | 7936 KB |
subtask2_12.txt | AC | 42 ms | 8704 KB |
subtask2_13.txt | AC | 40 ms | 8192 KB |