Submission #857211


Source Code Expand

Copy
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<utility>
#include<set>
#include<stack>
#include<list>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<cmath>
#include<cctype>


#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ren(i,a,b) for(int i=a;i>=b;i--)
#define ff first
#define ss second
#define pll pair<long long int,long long int>
#define pii pair<int,int>
#define vll vector<long long int>
#define vii vector<int>
#define gi(n) scanf("%d",&n)
#define gll(n) scanf("%lld",&n)
#define gstr(n) scanf("%s",n)
#define gl(n) cin >> n
#define oi(n) printf("%d",n)
#define oll(n) printf("%lld",n)
#define ostr(n) printf("%s",n)
#define ol(n) cout << n
#define os cout<<" "
#define on cout<<"\n"
#define o2(a,b) cout<<a<<" "<<b
#define all(n) n.begin(),n.end()
#define present(s,x) (s.find(x) != s.end())
#define cpresent(s,x) (find(all(s),x) != s.end())
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
using namespace std;

typedef unsigned long long int ull;
typedef long long int ll;
typedef vector<vector<ll> > mat;

int to[25][100005];

int main()
{ios_base::sync_with_stdio(false);
int n;
ll a[100005],len,q;

cin>>n;
rep(i,1,n)cin>>a[i];

cin>>len>>q;

rep(i,1,n-1)
{
	int lo=i+1,hi=n,mid;
	while(lo<hi)
	{
		mid=(lo+hi)/2;
		if(a[mid]-a[i]<=len)
		lo=mid+1;
		else
		hi=mid;
	}
	if(a[lo]-a[i]>len)lo--;
	to[0][i]=lo;
}
to[0][n]=n;

rep(i,1,24)
{
	rep(j,1,n)
	to[i][j]=to[i-1][to[i-1][j]];
}

while(q--)
{
	int l,r;
	cin>>l>>r;
	if(l>r)
	swap(l,r);
	int ans=0,ptr=l;
	ren(i,24,0)
	{
		if(to[i][ptr]<=r)
		{
			ans+=(1<<i);
			ptr=to[i][ptr];
		}
	}
	if(ptr!=r)ans++;
	ol(ans);on;
}

return 0;
}

Submission Info

Submission Time
Task E - Tak and Hotels
User abisheka
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1962 Byte
Status
Exec Time 903 ms
Memory 11392 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 example_01.txt
Subtask1 0 / 200 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 0 / 500 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 4 ms 384 KB
subtask1_01.txt 4 ms 384 KB
subtask1_02.txt 4 ms 384 KB
subtask1_03.txt 12 ms 512 KB
subtask1_04.txt 11 ms 512 KB
subtask1_05.txt 12 ms 512 KB
subtask1_06.txt 8 ms 384 KB
subtask1_07.txt 8 ms 384 KB
subtask1_08.txt 12 ms 512 KB
subtask1_09.txt 11 ms 512 KB
subtask1_10.txt 12 ms 512 KB
subtask1_11.txt 12 ms 512 KB
subtask1_12.txt 12 ms 512 KB
subtask1_13.txt 12 ms 512 KB
subtask2_01.txt 869 ms 11264 KB
subtask2_02.txt 881 ms 11392 KB
subtask2_03.txt 863 ms 11136 KB
subtask2_04.txt 465 ms 7424 KB
subtask2_05.txt 489 ms 7552 KB
subtask2_06.txt 705 ms 11008 KB
subtask2_07.txt 758 ms 11264 KB
subtask2_08.txt 903 ms 11392 KB
subtask2_09.txt 764 ms 11392 KB
subtask2_10.txt 776 ms 11392 KB
subtask2_11.txt 763 ms 10624 KB
subtask2_12.txt 681 ms 11392 KB
subtask2_13.txt 740 ms 11008 KB