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
Task E - Tak and Hotels
User LiChenKoh
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1655 Byte
Status AC
Exec Time 624 ms
Memory 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

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
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 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