Submission #857947


Source Code Expand

Copy
//It’s never too late to become what you might have been....
 #include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define inf 1000000000000
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define S second
#define F first
#define boost1 ios::sync_with_stdio(false);
#define boost2 cin.tie(0);
#define mem(a,val) memset(a,val,sizeof a)
#define endl "\n"
#define maxn 100001

ll dp[maxn][25],l,r,a[maxn];
int ok(ll x)
{
	ll cur=l;
	for(ll j=20;j>=0;j--)
	{
		if(x&(1<<j))
		cur=dp[cur][j];
	}
	return cur>=r;
}
int main()
{
	boost1;boost2;	
	ll i,j,n,x,y,lo,mid,hi,ind,q,L;
	cin>>n;
	for(i=1;i<=n;i++)
	cin>>a[i];
	cin>>L;
	for(i=1;i<=n;i++)
	{
		x=a[i]+L;
		if(a[n]<=x)
		dp[i][0]=n;
		else
		{
			ind=lower_bound(a+1,a+n+1,x)-a;
			if(a[ind]>x)
			ind--;
			assert(a[ind]<=x);
			dp[i][0]=ind;
		}
	}
	for(j=1;j<20;j++)
	{
		for(i=1;i<=n;i++)
		dp[i][j]=dp[dp[i][j-1]][j-1];
	}
	cin>>q;
	while(q--)
	{
		cin>>l>>r;
		if(l>r)
		swap(l,r);
		lo=0;
		hi=n;
		while(hi-lo>1)
		{
			mid=(lo+hi)/2;
			if(ok(mid))
			hi=mid;
			else
			lo=mid;
		}
		cout<<hi<<endl;
	}
	return 0;
}

Submission Info

Submission Time
Task E - Tak and Hotels
User shubhamgoyal__
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1241 Byte
Status AC
Exec Time 474 ms
Memory 21120 KB

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 4 ms 256 KB
subtask1_01.txt AC 4 ms 256 KB
subtask1_02.txt AC 4 ms 256 KB
subtask1_03.txt AC 6 ms 512 KB
subtask1_04.txt AC 6 ms 512 KB
subtask1_05.txt AC 6 ms 512 KB
subtask1_06.txt AC 5 ms 384 KB
subtask1_07.txt AC 5 ms 384 KB
subtask1_08.txt AC 6 ms 512 KB
subtask1_09.txt AC 6 ms 512 KB
subtask1_10.txt AC 6 ms 512 KB
subtask1_11.txt AC 6 ms 512 KB
subtask1_12.txt AC 6 ms 512 KB
subtask1_13.txt AC 8 ms 512 KB
subtask2_01.txt AC 379 ms 20992 KB
subtask2_02.txt AC 474 ms 21120 KB
subtask2_03.txt AC 284 ms 20992 KB
subtask2_04.txt AC 141 ms 13696 KB
subtask2_05.txt AC 165 ms 13824 KB
subtask2_06.txt AC 207 ms 20736 KB
subtask2_07.txt AC 327 ms 20992 KB
subtask2_08.txt AC 396 ms 21120 KB
subtask2_09.txt AC 399 ms 21120 KB
subtask2_10.txt AC 405 ms 21120 KB
subtask2_11.txt AC 418 ms 19456 KB
subtask2_12.txt AC 205 ms 21120 KB
subtask2_13.txt AC 210 ms 20736 KB