#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> pii;
const int C = 40;
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<int> > state_tim;
vector<vector<vector<int> > > state_set;
vector<vector<pii> > individ_updates;
void init(int N, int D, int H[]) {
n = N;
individ_updates.resize(n);
state_tim.resize(n);
state_set.resize(n);
heights.resize(N);
for (int i = 0; i < n; i++)
{
heights[i] = H[i];
state_tim[i].push_back(-1);
state_set[i].push_back(vector<int>());
}
d = D;
}
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) {
state_tim[a].push_back(i);
state_set[a].push_back(vector<int>(all(guys[a])));
time_since_last[a] = 0;
}
if (time_since_last[b] == C) {
state_tim[b].push_back(i);
state_set[b].push_back(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) {
int check_tim_idx = upper_bound(all(state_tim[x]), v) - state_tim[x].begin() - 1;
set<int> guys(all(state_set[x][check_tim_idx]));
int idx = lower_bound(all(individ_updates[x]),
pii(state_tim[x][check_tim_idx], 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:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for (int i = 0; i < first.size(); i++)
| ~~^~~~~~~~~~~~~~
potion.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for (int i = 0; i <second.size(); i++)
| ~~^~~~~~~~~~~~~~
potion.cpp:25:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | while (pnt1 < first.size() and pnt2 < second.size()) {
| ~~~~~^~~~~~~~~~~~~~
potion.cpp:25:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | while (pnt1 < first.size() and pnt2 < second.size()) {
| ~~~~~^~~~~~~~~~~~~~~
potion.cpp:28:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | if (pnt1 + 1 == first.size())
| ~~~~~~~~~^~~~~~~~~~~~~~~
potion.cpp:30:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | else if (pnt2 + 1 == second.size())
| ~~~~~~~~~^~~~~~~~~~~~~~~~
potion.cpp: In function 'std::vector<int> get_set(int, int)':
potion.cpp:103: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]
103 | 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 |
2 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 |
21 ms |
19780 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
268 ms |
47940 KB |
Output is correct |
| 2 |
Correct |
293 ms |
47576 KB |
Output is correct |
| 3 |
Correct |
271 ms |
27012 KB |
Output is correct |
| 4 |
Correct |
2036 ms |
22812 KB |
Output is correct |
| 5 |
Correct |
616 ms |
30300 KB |
Output is correct |
| 6 |
Execution timed out |
3022 ms |
40468 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
263 ms |
47548 KB |
Output is correct |
| 2 |
Correct |
2727 ms |
35396 KB |
Output is correct |
| 3 |
Correct |
1348 ms |
37140 KB |
Output is correct |
| 4 |
Execution timed out |
3072 ms |
40428 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
3928 KB |
Output is correct |
| 2 |
Incorrect |
82 ms |
2904 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 |
2 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 |
21 ms |
19780 KB |
Output is correct |
| 6 |
Correct |
268 ms |
47940 KB |
Output is correct |
| 7 |
Correct |
293 ms |
47576 KB |
Output is correct |
| 8 |
Correct |
271 ms |
27012 KB |
Output is correct |
| 9 |
Correct |
2036 ms |
22812 KB |
Output is correct |
| 10 |
Correct |
616 ms |
30300 KB |
Output is correct |
| 11 |
Execution timed out |
3022 ms |
40468 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
