Submission #857323


Source Code Expand

Copy
#include <bits/stdc++.h>


using namespace std;

const int MAXN = 100002;
int N,L,Q;
int x[MAXN]={0};
int a,b;
vector<int> dis[MAXN];

void solve(){
	cin>>N;
	for (int i=1;i<=N;i++)
		cin>>x[i];
	cin>>L;

	for (int i=1;i<=N;i++){
		dis[i].push_back(i);
		int lastNode = x[i];
		int lastDis = 0;
		for (int j=i+1;j<=N;j++){
			if (x[j]-lastNode<=L){
				;
			}
			else{
				lastDis += 1;
				lastNode = x[j-1];
				dis[i].push_back(j-1);
			}
		}
	}
	/*
	for (int i=1;i<=N;i++){
		for (auto j:dis[i])
			cout<<j<<" ";
		cout<<endl;
	}
	cout<<endl;
	*/

	cin>>Q;
	for (int i=1;i<=Q;i++){
		cin>>a>>b;
		if (a>b)
			swap(a,b);
		auto it = lower_bound(dis[a].begin(),dis[a].end(),b);
//		cout<<*it<<endl;
		cout<<(int)(it - dis[a].begin())<<endl;
	}
}


int main(){
//	freopen("in.txt","r",stdin);
	std::ios::sync_with_stdio(false);

//	int TestCase;
//	cin>>TestCase;
//	for (int i=0;i<TestCase;i++){
		solve();
//	}

	return 0;
}

Submission Info

Submission Time
Task E - Tak and Hotels
User zornlemma
Language C++14 (GCC 5.4.1)
Score 200
Code Size 993 Byte
Status TLE
Exec Time 3235 ms
Memory 824824 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 200 / 200 0 / 500
Status
AC × 1
AC × 14
AC × 14
TLE × 13
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 7 ms 2560 KB
subtask1_01.txt AC 7 ms 2560 KB
subtask1_02.txt AC 7 ms 2560 KB
subtask1_03.txt AC 16 ms 2816 KB
subtask1_04.txt AC 26 ms 5248 KB
subtask1_05.txt AC 17 ms 2688 KB
subtask1_06.txt AC 14 ms 3328 KB
subtask1_07.txt AC 11 ms 2688 KB
subtask1_08.txt AC 17 ms 2688 KB
subtask1_09.txt AC 18 ms 3200 KB
subtask1_10.txt AC 23 ms 4480 KB
subtask1_11.txt AC 25 ms 4480 KB
subtask1_12.txt AC 23 ms 4480 KB
subtask1_13.txt AC 22 ms 4352 KB
subtask2_01.txt TLE 3191 ms 390016 KB
subtask2_02.txt TLE 3233 ms 822392 KB
subtask2_03.txt TLE 3166 ms 140288 KB
subtask2_04.txt TLE 3153 ms 4992 KB
subtask2_05.txt TLE 3186 ms 340096 KB
subtask2_06.txt TLE 3153 ms 3712 KB
subtask2_07.txt TLE 3186 ms 340224 KB
subtask2_08.txt TLE 3201 ms 498168 KB
subtask2_09.txt TLE 3201 ms 497144 KB
subtask2_10.txt TLE 3202 ms 506616 KB
subtask2_11.txt TLE 3212 ms 599420 KB
subtask2_12.txt TLE 3235 ms 824824 KB
subtask2_13.txt TLE 3153 ms 3712 KB