Submission #856622


Source Code Expand

Copy
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstdlib>
#define INF 100000000
#define _INF -100000000
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> P;

static const int NN = 1e5 + 5;
int N, L, Q;
vi x(NN);
map<P, int> mp;

void solve(int a, int b) {
	if (mp[{a, b}] != 0) {
		cout << mp[{a, b}] << endl;
		return;
	}
	int ans = 1;
	int focus = a;
	int d = 0;
	//greedy
	while (focus < b) {
		if (d + x[focus + 1] - x[focus] <= L) {
			mp[{a, focus + 1}] = ans;
			d += x[focus + 1] - x[focus];
			focus++;
		}
		else {
			ans++;
			d = 0;
		}
	}
	cout << ans << endl;
}


int main() {
	cin >> N;
	Loop1(i, N) cin >> x[i];
	cin >> L >> Q;
	Loop(i, Q) {
		int a, b;
		cin >> a >> b;
		if (a > b) swap(a, b);
		solve(a, b);
	}
	return 0;
}

Submission Info

Submission Time
Task E - Tak and Hotels
User mao
Language C++14 (GCC 5.4.1)
Score 200
Code Size 1297 Byte
Status TLE
Exec Time 3189 ms
Memory 372096 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 5 ms 640 KB
subtask1_01.txt AC 5 ms 640 KB
subtask1_02.txt AC 4 ms 640 KB
subtask1_03.txt AC 92 ms 13440 KB
subtask1_04.txt AC 95 ms 13952 KB
subtask1_05.txt AC 95 ms 14080 KB
subtask1_06.txt AC 29 ms 4096 KB
subtask1_07.txt AC 30 ms 4224 KB
subtask1_08.txt AC 94 ms 13824 KB
subtask1_09.txt AC 97 ms 14208 KB
subtask1_10.txt AC 99 ms 14080 KB
subtask1_11.txt AC 102 ms 14592 KB
subtask1_12.txt AC 99 ms 14080 KB
subtask1_13.txt AC 85 ms 12160 KB
subtask2_01.txt TLE 3180 ms 295936 KB
subtask2_02.txt TLE 3185 ms 355840 KB
subtask2_03.txt TLE 3178 ms 279680 KB
subtask2_04.txt TLE 3185 ms 353792 KB
subtask2_05.txt TLE 3187 ms 372096 KB
subtask2_06.txt TLE 3182 ms 319360 KB
subtask2_07.txt TLE 3188 ms 347520 KB
subtask2_08.txt TLE 3181 ms 308864 KB
subtask2_09.txt TLE 3181 ms 306944 KB
subtask2_10.txt TLE 3182 ms 269312 KB
subtask2_11.txt TLE 3179 ms 279168 KB
subtask2_12.txt TLE 3189 ms 285056 KB
subtask2_13.txt TLE 3179 ms 279680 KB