#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> pii;
const int C = 20;
struct checkpoint {
int time;
vector<int> guys;
checkpoint() {}
checkpoint(int T, vector<int> sett) {
time = T;
guys = sett;
}
bool operator<(const checkpoint &a) const {return time < a.time;}
};
int n, d, u;
vector<int> heights;
vector<pii> changes;
int min_dist(vector<int> first, vector<int> second) {
if (first.empty() || second.empty())
return 1e9;
for (int i = 0; i < first.size(); i++)
first[i] = heights[first[i]];
for (int i = 0; i <second.size(); i++)
second[i] = heights[second[i]];
sort(all(first));
sort(all(second));
int pnt1 = 0, pnt2 = 0, out = 2e9;
while (pnt1 < first.size() and pnt2 < second.size()) {
out = min(out, abs(first[pnt1] - second[pnt2]));
if (pnt1 + 1 == first.size())
pnt2++;
else if (pnt2 + 1 == second.size())
pnt1++;
else if (first[pnt1] < second[pnt2])
pnt1++;
else
pnt2++;
}
return out;
}
vector<vector<checkpoint> > states;
vector<vector<pii> > individ_updates;
void init(int N, int D, int H[]) {
n = N;
individ_updates.resize(n);
states.resize(n);
heights.resize(N);
for (int i = 0; i < n; i++)
{
heights[i] = H[i];
states[i].push_back(checkpoint(-1, vector<int>()));
}
d = D;
states.resize(n);
}
void process(set<int> &set, int &val) {
if (set.count(val))
set.erase(val);
else
set.insert(val);
}
void curseChanges(int U, int A[], int B[]) {
u = U;
changes.resize(u);
for (int i = 0; i < u; i++)
{
changes[i].first = A[i], changes[i].second = B[i];
individ_updates[A[i]].push_back({i, B[i]});
individ_updates[B[i]].push_back({i, A[i]});
}
vector<int> time_since_last(n, 0);
vector<set<int> > guys(n);
for (int i = 0; i < u; i++) {
int a = changes[i].first, b = changes[i].second;
process(guys[a], b);
process(guys[b], a);
if (time_since_last[a] == C) {
states[a].push_back(checkpoint(i, vector<int>(all(guys[a]))));
time_since_last[a] = 0;
}
if (time_since_last[b] == C) {
states[b].push_back(checkpoint(i, vector<int>(all(guys[b]))));
time_since_last[b] = 0;
}
time_since_last[a]++;
time_since_last[b]++;
}
}
// todo; finish get set
vector<int> get_set(int x, int v) {
checkpoint check = *prev(upper_bound(all(states[x]), checkpoint(v, vector<int>())));
set<int> guys(all(check.guys));
int idx = lower_bound(all(individ_updates[x]), pii(check.time, 1e9)) - individ_updates[x].begin();
for (; idx < individ_updates[x].size() and individ_updates[x][idx].first < v; idx++)
process(guys, individ_updates[x][idx].second);
return vector<int>(all(guys));
}
int question(int x, int y, int v) {
vector<int> x_set = get_set(x, v), y_set = get_set(y, v);
return min_dist(x_set, y_set);
}
Compilation message
potion.cpp: In function 'int min_dist(std::vector<int>, std::vector<int>)':
potion.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (int i = 0; i < first.size(); i++)
| ~~^~~~~~~~~~~~~~
potion.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for (int i = 0; i <second.size(); i++)
| ~~^~~~~~~~~~~~~~
potion.cpp:37:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | while (pnt1 < first.size() and pnt2 < second.size()) {
| ~~~~~^~~~~~~~~~~~~~
potion.cpp:37:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | while (pnt1 < first.size() and pnt2 < second.size()) {
| ~~~~~^~~~~~~~~~~~~~~
potion.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | if (pnt1 + 1 == first.size())
| ~~~~~~~~~^~~~~~~~~~~~~~~
potion.cpp:42:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | else if (pnt2 + 1 == second.size())
| ~~~~~~~~~^~~~~~~~~~~~~~~~
potion.cpp: In function 'std::vector<int> get_set(int, int)':
potion.cpp:109:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for (; idx < individ_updates[x].size() and individ_updates[x][idx].first < v; idx++)
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
600 KB |
Output is correct |
| 3 |
Correct |
2 ms |
600 KB |
Output is correct |
| 4 |
Correct |
19 ms |
15688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
257 ms |
44140 KB |
Output is correct |
| 2 |
Correct |
235 ms |
44048 KB |
Output is correct |
| 3 |
Correct |
223 ms |
24008 KB |
Output is correct |
| 4 |
Correct |
2020 ms |
28292 KB |
Output is correct |
| 5 |
Correct |
603 ms |
31272 KB |
Output is correct |
| 6 |
Execution timed out |
3066 ms |
43920 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
220 ms |
43768 KB |
Output is correct |
| 2 |
Execution timed out |
3023 ms |
39900 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
3420 KB |
Output is correct |
| 2 |
Incorrect |
69 ms |
2388 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
600 KB |
Output is correct |
| 3 |
Correct |
1 ms |
600 KB |
Output is correct |
| 4 |
Correct |
2 ms |
600 KB |
Output is correct |
| 5 |
Correct |
19 ms |
15688 KB |
Output is correct |
| 6 |
Correct |
257 ms |
44140 KB |
Output is correct |
| 7 |
Correct |
235 ms |
44048 KB |
Output is correct |
| 8 |
Correct |
223 ms |
24008 KB |
Output is correct |
| 9 |
Correct |
2020 ms |
28292 KB |
Output is correct |
| 10 |
Correct |
603 ms |
31272 KB |
Output is correct |
| 11 |
Execution timed out |
3066 ms |
43920 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
