Submission #855735


Source Code Expand

Copy
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(a) (a).begin(), (a).end()

using namespace std;

int nextInt() {int a; cin >> a; return a;}
char nextChar() {char a; cin >> a; return a;}
double nextDouble() {double a; cin >> a; return a;}
string nextString() {string a; cin >> a; return a;}

void inputVector(vector<int> &v, int &n) {rep(i,n){v.push_back(nextInt());}}
void inputVector(vector<double> &v, int &n) {rep(i,n){v.push_back(nextDouble());}}
void inputVector(vector<string> &v, int &n) {rep(i,n){v.push_back(nextString());}}

signed main() {
	int N;
	cin >> N;

	vector<int> x;
	inputVector(x, N);

	vector<int> nx(N);
	int L, Q;
	cin >> L >> Q;

	if (N > 1000 || Q > 1000) {
		cout << 0 << endl;
		return 0;
	}

	for (int i = 0; i < N; i++) {
		int pt = i;
		while (pt < N && x[pt] - x[i] <= L) {
			pt++;
		}
		nx[i] = pt - 1;
	}

	rep(loop, Q) {
		int a, b;
		cin >> a >> b;
		a--; b--;

		if (a > b) {
			swap(a, b);
		}
		
		int ret = 0;
		while (a < b) {
			a = nx[a];
			ret++;
		}

		cout << ret << endl;
	}

    return 0;
}

Submission Info

Submission Time
Task E - Tak and Hotels
User iwashi31
Language C++14 (GCC 5.4.1)
Score 200
Code Size 1470 Byte
Status
Exec Time 79 ms
Memory 1908 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 example_01.txt
Subtask1 200 / 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 256 KB
subtask1_01.txt 5 ms 256 KB
subtask1_02.txt 4 ms 256 KB
subtask1_03.txt 12 ms 256 KB
subtask1_04.txt 14 ms 256 KB
subtask1_05.txt 13 ms 256 KB
subtask1_06.txt 8 ms 256 KB
subtask1_07.txt 9 ms 256 KB
subtask1_08.txt 12 ms 256 KB
subtask1_09.txt 13 ms 256 KB
subtask1_10.txt 12 ms 256 KB
subtask1_11.txt 14 ms 256 KB
subtask1_12.txt 12 ms 256 KB
subtask1_13.txt 13 ms 256 KB
subtask2_01.txt 58 ms 1908 KB
subtask2_02.txt 78 ms 1908 KB
subtask2_03.txt 79 ms 1908 KB
subtask2_04.txt 53 ms 1400 KB
subtask2_05.txt 53 ms 1400 KB
subtask2_06.txt 78 ms 1908 KB
subtask2_07.txt 79 ms 1908 KB
subtask2_08.txt 73 ms 1908 KB
subtask2_09.txt 73 ms 1908 KB
subtask2_10.txt 76 ms 1908 KB
subtask2_11.txt 72 ms 1780 KB
subtask2_12.txt 72 ms 1908 KB
subtask2_13.txt 79 ms 1908 KB