Submission #856170


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  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,start[maxn],finish[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++;
		start[block_no]=i;
		for(j=i;j<=min(n,i+sz-1);j++)
		block[j]=i;
		finish[block_no]=min(n,i+sz-1);
		i=i+sz-1;
	}
	for(i=n;i>=1;i--)
	{
		x=a[i]+L;
		if(a[n]<=a[i]+L)
		ind=n;
		else
		{
			ind=lower_bound(a+1,a+n+1,x)-a;
			if(a[ind]>a[i]+L)
			ind--;
		}	
		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;
			if(a[n]<=a[curl]+L)
			curl=n;
			else
			{
				ind=lower_bound(a+1,a+n+1,x)-a;
				if(a[ind]>a[curl]+L)
				ind--;
				curl=ind;
			}
			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 1690 Byte
Status TLE
Exec Time 3157 ms
Memory 2432 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 256 KB
subtask1_04.txt AC 13 ms 256 KB
subtask1_05.txt AC 5 ms 256 KB
subtask1_06.txt AC 6 ms 256 KB
subtask1_07.txt AC 4 ms 256 KB
subtask1_08.txt TLE 3153 ms 256 KB
subtask1_09.txt AC 5 ms 256 KB
subtask1_10.txt AC 9 ms 256 KB
subtask1_11.txt AC 9 ms 256 KB
subtask1_12.txt AC 9 ms 256 KB
subtask1_13.txt AC 12 ms 256 KB
subtask2_01.txt AC 327 ms 2304 KB
subtask2_02.txt AC 2069 ms 2432 KB
subtask2_03.txt AC 247 ms 2176 KB
subtask2_04.txt TLE 3157 ms 1280 KB
subtask2_05.txt AC 225 ms 1664 KB
subtask2_06.txt TLE 3153 ms 1792 KB
subtask2_07.txt AC 411 ms 2304 KB
subtask2_08.txt AC 1489 ms 2432 KB
subtask2_09.txt AC 1470 ms 2432 KB
subtask2_10.txt AC 1470 ms 2432 KB
subtask2_11.txt AC 1455 ms 2304 KB
subtask2_12.txt AC 729 ms 2432 KB
subtask2_13.txt TLE 3153 ms 1792 KB