using namespace std;
#include <iostream>
#include <vector>
#define pi pair<int,int>
#define vi vector<int>
#define ll long long
#include <algorithm>
#include <set>
#include <map>
const int siz = 1e5;
vector<set<int>> f(siz);
//pi padre[siz];
//int ans[siz];
int h[siz];
vector<pi> fi[siz];
vector<vector<set<int>>> v(1001);
map<pi, bool> fr;
vi fn[siz];
//bool ch[siz];
const ll m = 1e9 + 7;
bool t;
int n;
void init(int N, int D, int F[]) {
n = N;
for (int i = 0; i < n; i++) {
h[i] = F[i];
}
}
void curseChanges(int U, int A[], int B[]) {
for (int i = 0; i < U; i++) {
if (f[A[i]].find(B[i]) == f[A[i]].end()) {
f[A[i]].insert(B[i]);
f[B[i]].insert(A[i]);
}
else {
f[A[i]].erase(B[i]);
f[B[i]].erase(A[i]);
}
v[i+1] = f;
}
for (int i = 0; i < n; i++) {
for (int t : f[i]) {
fi[i].push_back({ h[t],t });
}
sort(fi[i].begin(), fi[i].end());
for (pi p : fi[i]) {
fn[i].push_back(p.first);
}
}
}
int question(int X, int Y, int V) {
set<int> t1 = v[V][X], t2 = v[V][Y];
vi v1, v2;
for (int i : t1) {
v1.push_back(h[i]);
}
for (int i : t2) {
v2.push_back(h[i]);
}
sort(v1.begin(), v1.end());
sort(v2.begin(),v2.end());
int siz1 = v1.size(), siz2 = v2.size();
int ans = 1e9;
for (int i = 0; i < siz1; i++) {
int in = upper_bound(v2.begin(), v2.end(), v1[i]) - v2.begin();
if (in > 0) {
ans = min(ans, abs(v1[i] - v2[in - 1]));
}
if (in < siz2) {
ans = min(ans, abs(v1[i] - v2[in ]));
}
}
return ans;
}
/*
int main() {
int N, D, U, Q;
std::ios::sync_with_stdio(false); std::cin.tie(NULL);
std::cin >> N >> D >> U >> Q;
int* F = new int[N];
for (int i = 0; i < N; i++)
std::cin >> F[i];
init(N, D, F);
int* A = new int[U], * B = new int[U];
for (int i = 0; i < U; i++) {
std::cin >> A[i] >> B[i];
}
curseChanges(U, A, B);
bool correct = true;
for (int i = 0; i < Q; i++) {
int X, Y, V, CorrectAnswer;
std::cin >> X >> Y >> V >> CorrectAnswer;
int YourAnswer = question(X, Y, V);
if (YourAnswer != CorrectAnswer) {
std::cout << "WA! Question: " << i
<< " (X=" << X << ", Y=" << Y << ", V=" << V << ") "
<< "Your answer: " << YourAnswer
<< " Correct Answer: " << CorrectAnswer << std::endl;
correct = false;
}
else {
std::cerr << YourAnswer << " - OK" << std::endl;
}
}
if (correct) {
std::cout << "Correct." << std::endl;
}
else std::cout << "Incorrect." << std::endl;
return 0;
}*/
// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu
// Tips for Getting Started:
// 1. Use the Solution Explorer window to add/manage files
// 2. Use the Team Explorer window to connect to source control
// 3. Use the Output window to see build output and other messages
// 4. Use the Error List window to view errors
// 5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
// 6. In the future, to open this project again, go to File > Open > Project and select the .sln file
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
61364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
108 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
157 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
141 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
107 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
61364 KB |
Output is correct |
| 2 |
Runtime error |
108 ms |
262144 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
