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

Submission #856733

Source Code Expand

Copy
```#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define PB push_back
#define MP make_pair
#define MOD 1000000007LL
#define endl "\n"
const ll UNDEF = -1;
const ll INF=1e18;
template<typename T> inline bool chkmax(T &aa, T bb) { return aa < bb ? aa = bb, true : false; }
template<typename T> inline bool chkmin(T &aa, T bb) { return aa > bb ? aa = bb, true : false; }
const ll mn=1e5+4;
ll p[mn];
const ll klim=32;
ll f[2][klim][mn];
ll solve(ll a, ll go, ll rev) {
ll origa=a;
for (ll k=0;k<klim;k++) {
if (go&(1LL<<k)) {
a=f[rev][k][a];
}
}
return a;
}
int main() {
ios_base::sync_with_stdio(false);
ll n; scanf("%lld",&n);
for (ll i=0;i<n;i++) scanf("%lld",&p[i]);
ll L,Q; scanf("%lld %lld",&L,&Q);
for (ll rev=0;rev<2;rev++) {
for (ll x=0;x<n;x++) {
ll px=p[x];
ll imin=x,imax=n;
while(imin<imax) {
ll imid=(imin+imax)/2;
if (p[imid]<=L+px) imin=imid+1;
else imax=imid;
}
imin--;
f[rev][0][x]=imin;
//printf("rev:%lld x:%lld imin:%lld\n",rev,x,imin);
}
for (ll k=1;k<klim;k++) {
for (ll x=0;x<n;x++) f[rev][k][x]=f[rev][k-1][f[rev][k-1][x]];
}
reverse(p,p+n);
for (ll i=0;i<n;i++) p[i]=-p[i];
}
for (ll i=0;i<Q;i++) {
ll a,b; scanf("%lld %lld",&a,&b);
a--;b--;
ll rev=0;
if (a>b) {
rev=1;
a=n-1-a;
b=n-1-b;
}
ll imin=0,imax=n+1;
while(imin<imax) {
ll imid=(imin+imax)/2;
if (solve(a,imid,rev)<b) imin=imid+1;
else imax=imid;
}
ll got=solve(a,imin,rev);
if (got>=b) printf("%lld\n",imin);
else printf("-1\n");
}
}```

#### Submission Info

Submission Time 2016-08-28 22:18:23+0900 E - Tak and Hotels LiChenKoh C++14 (GCC 5.4.1) 700 1655 Byte AC 624 ms 51584 KB

#### Compile Error

```./Main.cpp: In function ‘int main()’:
./Main.cpp:29:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
ll n; scanf("%lld",&n);
^
./Main.cpp:30:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for (ll i=0;i<n;i++) scanf("%lld",&p[i]);
^
./Main.cpp:31:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
ll L,Q; scanf("%lld %lld",&L,&Q);
^
./Main.cpp:52:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
ll a,b; scanf("%lld %lld",&a,&b);
^
```

#### Judge Result

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 5 ms 512 KB
subtask1_01.txt AC 5 ms 512 KB
subtask1_02.txt AC 5 ms 512 KB
subtask1_03.txt AC 7 ms 1024 KB
subtask1_04.txt AC 8 ms 1024 KB
subtask1_05.txt AC 8 ms 1024 KB
subtask1_06.txt AC 6 ms 768 KB
subtask1_07.txt AC 6 ms 768 KB
subtask1_08.txt AC 7 ms 1024 KB
subtask1_09.txt AC 8 ms 1024 KB
subtask1_10.txt AC 7 ms 1024 KB
subtask1_11.txt AC 8 ms 1024 KB
subtask1_12.txt AC 8 ms 1024 KB
subtask1_13.txt AC 7 ms 1024 KB
subtask2_01.txt AC 530 ms 51456 KB
subtask2_02.txt AC 595 ms 51584 KB
subtask2_03.txt AC 459 ms 51456 KB
subtask2_04.txt AC 210 ms 33920 KB
subtask2_05.txt AC 283 ms 34048 KB
subtask2_06.txt AC 310 ms 51200 KB
subtask2_07.txt AC 601 ms 51456 KB
subtask2_08.txt AC 624 ms 51584 KB
subtask2_09.txt AC 589 ms 51584 KB
subtask2_10.txt AC 587 ms 51584 KB
subtask2_11.txt AC 558 ms 47872 KB
subtask2_12.txt AC 296 ms 51584 KB
subtask2_13.txt AC 311 ms 51200 KB