Submission #1169879

#TimeUsernameProblemLanguageResultExecution timeMemory
1169879jbarejaTwo Antennas (JOI19_antennas)C++20
2 / 100
3095 ms3512 KiB
#include <bits/stdc++.h>

using namespace std;

int N; // liczba anten
int Q; // liczba zapytań
vector<pair<int, pair<int, int>>> antennas; // < H — wysokość anteny, < A, B — przedział odległości, z którymi może się komunikować > >

int communication_cost(int i, int j) {
	const int H1 = antennas[i].first;
	const int A1 = antennas[i].second.first;
	const int B1 = antennas[i].second.second;
	const int H2 = antennas[j].first;
	const int A2 = antennas[j].second.first;
	const int B2 = antennas[j].second.second;
	int dist = abs(i - j);
	if (A1 <= dist && dist <= B1 && A2 <= dist && dist <= B2) return abs(H1 - H2);
	return -1;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i=0; i<N; i++) {
		int H, A, B;
		cin >> H >> A >> B;
		antennas.push_back({H, { A, B } });
	}

	// vector<vector<int>> cost(N, vector<int>(N, -1));
	// for (int i=0; i<N-1; i++) {
	// 	for (int j=i+1; j<N; j++) {
	// 		cost[i][j] = communication_cost(i, j);
	// 		cost[j][i] = cost[i][j];
	// 	}
	// }

	cin >> Q;
	for (int i=0; i<Q; i++) {
		int L, R;
		cin >> L >> R;
		L--, R--;
		int max_cost = -1;
		for (int j=L; j<R; j++) for (int k=j+1; k<=R; k++) max_cost = max(max_cost, communication_cost(j, k));
		cout << max_cost << '\n';
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...