Submission #856539


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 a[maxn],block[maxn],block_no,store[maxn],sz=400,cnt[maxn],nxt[maxn];
int main()
{
	boost1;boost2;	
	ll i,j,n,q,x,y,l,r,L,curl,ind,ctr=0;
	cin>>n;
	for(i=1;i<=n;i++)
	cin>>a[i];
	cin>>L;
	for(i=1;i<=n;i++)
	{
		block_no++;
		for(j=i;j<=min(n,i+sz-1);j++)
		block[j]=i;
		i=i+sz-1;
	}
	for(i=1;i<=n;i++)
	{
		x=a[i]+L;
		if(a[n]<=a[i]+L)
		store[i]=n;
		else
		{
			ind=lower_bound(a+1,a+n+1,x)-a;
			if(a[ind]>a[i]+L)
			ind--;
			store[i]=ind;
		}	
	}
	for(i=n+1;i<=n+500;i++)
	store[i]=n;
	for(i=n;i>=1;i--)
	{
		x=a[i]+L;	
		ind=store[i];
		if(block[ind]!=block[i])
		{
			cnt[i]=1;
			nxt[i]=ind;
		}
		else
		{
			cnt[i]=cnt[ind]+1;
			nxt[i]=nxt[ind];
		}
	}
	cin>>q;
	while(q--)
	{
		cin>>l>>r;
		if(l>r)
		swap(l,r);
		ctr=0;
		curl=l;
		if(block[l]!=block[r])
		{
			curl=l;
			ctr=cnt[curl];
			curl=nxt[curl];
		}
		while(1)
		{
			if(block[curl]==block[r])
			break;
			ctr+=cnt[curl];
			curl=nxt[curl];
		}
		while(1)
		{
			if(curl>=r)
			{
				cout<<ctr<<endl;
				break;
			}
			x=a[curl]+L;
			curl=store[curl];
			ctr++;
		}
	}
	return 0;
}

Submission Info

Submission Time
Task E - Tak and Hotels
User shubhamgoyal__
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1624 Byte
Status TLE
Exec Time 3157 ms
Memory 4736 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 200 0 / 500
Status
AC × 1
AC × 13
TLE × 1
AC × 23
TLE × 4
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 5 ms 384 KB
subtask1_04.txt AC 5 ms 384 KB
subtask1_05.txt AC 5 ms 384 KB
subtask1_06.txt AC 5 ms 256 KB
subtask1_07.txt AC 5 ms 256 KB
subtask1_08.txt TLE 3157 ms 256 KB
subtask1_09.txt AC 5 ms 384 KB
subtask1_10.txt AC 5 ms 384 KB
subtask1_11.txt AC 5 ms 384 KB
subtask1_12.txt AC 5 ms 384 KB
subtask1_13.txt AC 5 ms 384 KB
subtask2_01.txt AC 213 ms 4608 KB
subtask2_02.txt AC 247 ms 4736 KB
subtask2_03.txt AC 259 ms 4480 KB
subtask2_04.txt TLE 3153 ms 2816 KB
subtask2_05.txt AC 100 ms 3200 KB
subtask2_06.txt TLE 3157 ms 4096 KB
subtask2_07.txt AC 213 ms 4608 KB
subtask2_08.txt AC 233 ms 4736 KB
subtask2_09.txt AC 231 ms 4736 KB
subtask2_10.txt AC 229 ms 4736 KB
subtask2_11.txt AC 211 ms 4480 KB
subtask2_12.txt AC 648 ms 4736 KB
subtask2_13.txt TLE 3153 ms 4096 KB