#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif
using namespace std;
/*
6 5 11 4
2 42 1000 54 68 234
0 1
2 0
3 4
3 5
3 5
1 3
5 3
0 5
3 0
1 3
3 5
0 3 4 26
3 0 8 0
0 5 5 1000000000
3 0 11 14
*/
namespace sOlUTiON {
using u32 = unsigned int;
// 282
using bit = array<u32, 283>;
constexpr int N = 1E5, M = 2E5;
int n, D;
int h[N];
vector<int> f[N];
vector<int> a[N];
bit compress(vector<int> &a) {
int j = 0, k = 0;
bit res{};
for (int i = 0; i < int(a.size()); i++) {
if (j + 18 <= 32) {
res[k] |= a[i] << j;
j += 18;
if (j == 32) {
j = 0;
k++;
}
} else {
res[k] |= a[i] << j;
int x = 32 - j;
j += 18;
j -= 32;
k++;
res[k] |= a[i] >> x;
}
}
res[282] = a.size();
return res;
}
vector<int> decompress(bit a) {
int n = a[282];
int j = 0, k = 0;
vector<int> ans(n);
for (int i = 0; i < n; i++) {
if (j + 18 <= 32) {
ans[i] = a[k] >> j;
j += 18;
if (j == 32) {
j = 0;
k++;
}
} else {
ans[i] |= a[k] >> j;
int x = 32 - j;
j += 18;
j -= 32;
k++;
ans[i] |= a[k] << x;
}
}
for (int &x : ans) x &= (1 << 18) - 1;
return ans;
}
};
using namespace sOlUTiON;
void init(int _N, int _D, int H[]) {
n = _N;
D = _D;
for (int i = 0; i < n; i++) {
h[i] = H[i];
}
}
bit get(vector<int> &a, int x) {
bit b{};
for (int i = 0; i < 283; i++) {
b[i] = a[x * 283 + i];
}
return b;
}
void curseChanges(int U, int A[], int B[]) {
int cnt[n] {};
for (int i = 0; i < U; i++) {
cnt[A[i]]++;
cnt[B[i]]++;
}
for (int i = 0; i < n; i++) {
a[i].reserve(283 * cnt[i]);
}
for (int i = 0; i < 50000; i++) cerr << endl;
for (int i = 0; i < U; i++) {
int u = A[i];
int v = B[i];
{
vector<int> b, w;
if (!a[u].empty()) {
b = decompress(get(a[u], a[u].size() / 283 - 1));
}
int j = 0;
while (j < int(b.size()) && (b[j] != v && h[b[j]] <= h[v]))
w.push_back(b[j++]);
if (j < int(b.size()) && b[j] == v) {
j++;
} else {
w.push_back(v);
}
while (j < int(b.size()))
w.push_back(b[j++]);
auto x = compress(w);
for (int i = 0; i < 283; i++) {
a[u].push_back(x[i]);
}
}
{
vector<int> b, w;
if (!a[v].empty()) {
b = decompress(get(a[v], a[v].size() / 283 - 1));
}
int j = 0;
while (j < int(b.size()) && (b[j] != u && h[b[j]] <= h[u]))
w.push_back(b[j++]);
if (j < int(b.size()) && b[j] == u) {
j++;
} else {
w.push_back(u);
}
while (j < int(b.size()))
w.push_back(b[j++]);
auto x = compress(w);
for (int i = 0; i < 283; i++) {
a[v].push_back(x[i]);
}
}
f[u].push_back(i + 1);
f[v].push_back(i + 1);
}
for (int i = 0; i < n; i++) {
assert(a[i].size() == a[i].capacity());
}
}
int question(int x, int y, int v) {
int p1 = upper_bound(f[x].begin(), f[x].end(), v) - f[x].begin() - 1;
int p2 = upper_bound(f[y].begin(), f[y].end(), v) - f[y].begin() - 1;
int ans = 1E9;
if (p1 == -1 || p2 == -1) {
return ans;
}
int s1 = a[x][283 * p1 + 282];
int s2 = a[y][283 * p2 + 282];
if (s1 == 0 || s2 == 0)
return ans;
vector<int> f = decompress(get(a[x], p1));
vector<int> s = decompress(get(a[y], p2));
int j = 0;
for (int i = 0; i < s1; i++) {
int t = h[f[i]];
while (j + 1 < s2 && h[s[j]] < t)
j++;
ans = min(ans, abs(h[f[i]] - h[s[j]]));
}
j = 0;
for (int i = 0; i < s2; i++) {
int t = h[s[i]];
while (j + 1 < s1 && h[f[j]] < t)
j++;
ans = min(ans, abs(h[s[i]] - h[f[j]]));
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
5052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
7240 KB |
Output is correct |
| 2 |
Correct |
68 ms |
7296 KB |
Output is correct |
| 3 |
Correct |
68 ms |
7268 KB |
Output is correct |
| 4 |
Correct |
78 ms |
8468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
161 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
150 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
174 ms |
27676 KB |
Output is correct |
| 2 |
Correct |
199 ms |
27548 KB |
Output is correct |
| 3 |
Correct |
205 ms |
27588 KB |
Output is correct |
| 4 |
Correct |
390 ms |
27872 KB |
Output is correct |
| 5 |
Correct |
347 ms |
27832 KB |
Output is correct |
| 6 |
Correct |
213 ms |
27460 KB |
Output is correct |
| 7 |
Correct |
324 ms |
27624 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
5052 KB |
Output is correct |
| 2 |
Correct |
65 ms |
7240 KB |
Output is correct |
| 3 |
Correct |
68 ms |
7296 KB |
Output is correct |
| 4 |
Correct |
68 ms |
7268 KB |
Output is correct |
| 5 |
Correct |
78 ms |
8468 KB |
Output is correct |
| 6 |
Runtime error |
161 ms |
262144 KB |
Execution killed with signal 9 |
| 7 |
Halted |
0 ms |
0 KB |
- |
