#include<vector>
#include<utility>
#include<cmath>
#include<algorithm>
using namespace std;
namespace cj{
vector<int> h, a, b;
int n, d, u, sqrtu;
vector<vector<vector<int>>> big;
vector<vector<pair<int,int>>> graph;
vector<vector<vector<pair<int,int>>>> small;
vector<int> bs;
bool Comp(pair<int,int> A, pair<int,int> B){
if (h[A.first] == h[B.first]){
return A.first < B.first;
}
return h[A.first] < h[B.first];
}
inline void push(vector<int> &V, int val){
if (V.empty()){
V.push_back(val);
}
else if (V.back() != val){
V.push_back(val);
}
else {
V.pop_back();
}
}
}
void init(int N, int D, int H[]) {
cj::n = N;
cj::d = D;
cj::h = vector<int>(N);
cj::graph = vector<vector<pair<int,int>>>(cj::n, vector<pair<int,int>>(0));
for (int i = 0; i < N; i++){
cj::h[i] = H[i];
}
}
void curseChanges(int U, int A[], int B[]) {
cj::u = U;
cj::a = cj::b = vector<int>(U);
for (int i = 0; i < U; i++){
cj::a[i] = A[i];
cj::b[i] = B[i];
}
cj::sqrtu = floor(sqrt(cj::u));
for (int i = 0; i < U; i++){
cj::graph[cj::a[i]].push_back({cj::b[i], i});
cj::graph[cj::b[i]].push_back({cj::a[i], i});
}
int p = 0;
while (p < U){
cj::bs.push_back(p);
p += cj::sqrtu;
}
cj::bs.push_back(cj::u);
for (int i = 0; i < cj::n; i++){
sort(cj::graph[i].begin(), cj::graph[i].end(), cj::Comp);
}
for (int i = 0; i < cj::bs.size() -1; i++){
cj::big.push_back(vector<vector<int>>(cj::n, vector<int>(0)));
cj::small.push_back(vector<vector<pair<int,int>>>(cj::n, vector<pair<int,int>>(0)));
for (int j = 0; j < cj::n; j++){
for (pair<int,int> k : cj::graph[j]){
if (cj::bs[i] <= k.second && cj::bs[i+1] > k.second){
cj::small[i][j].push_back(k);
}
if (cj::bs[i] > k.second){
cj::push(cj::big[i][j], k.first);
}
}
}
}
}
int question(int x, int y, int v) {
v--;
if (v == -1) return 1e9;
int slot;
for (int i = cj::bs.size() - 1; i >= 0; i--){
if (cj::bs[i] <= v){
slot = i;
break;
}
}
vector<int> xseq, yseq;
int p1 = 0, p2 = 0;
while (p1 != cj::big[slot][x].size() || p2 != cj::small[slot][x].size()){
if (p1 == cj::big[slot][x].size()){
if (cj::small[slot][x][p2].second <= v) cj::push(xseq, cj::small[slot][x][p2].first);
p2++;
}
else if (p2 == cj::small[slot][x].size()){
cj::push(xseq, cj::big[slot][x][p1]);
p1++;
}
else if (cj::h[cj::big[slot][x][p1]] <= cj::h[cj::small[slot][x][p2].first]){
cj::push(xseq, cj::big[slot][x][p1]);
p1++;
}
else {
if (cj::small[slot][x][p2].second <= v) cj::push(xseq, cj::small[slot][x][p2].first);
p2++;
}
}
p1 = 0;
p2 = 0;
while (p1 != cj::big[slot][y].size() || p2 != cj::small[slot][y].size()){
if (p1 == cj::big[slot][y].size()){
if (cj::small[slot][y][p2].second <= v) cj::push(yseq, cj::small[slot][y][p2].first);
p2++;
}
else if (p2 == cj::small[slot][y].size()){
cj::push(yseq, cj::big[slot][y][p1]);
p1++;
}
else if (cj::h[cj::big[slot][y][p1]] <= cj::h[cj::small[slot][y][p2].first]){
cj::push(yseq, cj::big[slot][y][p1]);
p1++;
}
else {
if (cj::small[slot][y][p2].second <= v) cj::push(yseq, cj::small[slot][y][p2].first);
p2++;
}
}
if (xseq.empty() || yseq.empty()){
return 1e9;
}
p1 = 0;
p2 = 0;
int output = 1e9+7;
while (p1 < xseq.size() && p2 < yseq.size()){
output = min(output, abs(cj::h[xseq[p1]] - cj::h[yseq[p2]]));
if (cj::h[xseq[p1]] <= cj::h[yseq[p2]]){
p1++;
}
else {
p2++;
}
}
return output;
}
Compilation message
potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (int i = 0; i < cj::bs.size() -1; i++){
| ~~^~~~~~~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:91:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | while (p1 != cj::big[slot][x].size() || p2 != cj::small[slot][x].size()){
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp:91:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | while (p1 != cj::big[slot][x].size() || p2 != cj::small[slot][x].size()){
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp:92:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | if (p1 == cj::big[slot][x].size()){
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp:96:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | else if (p2 == cj::small[slot][x].size()){
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp:111:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | while (p1 != cj::big[slot][y].size() || p2 != cj::small[slot][y].size()){
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp:111:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | while (p1 != cj::big[slot][y].size() || p2 != cj::small[slot][y].size()){
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp:112:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | if (p1 == cj::big[slot][y].size()){
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp:116:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | else if (p2 == cj::small[slot][y].size()){
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp:135:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | while (p1 < xseq.size() && p2 < yseq.size()){
| ~~~^~~~~~~~~~~~~
potion.cpp:135:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | while (p1 < xseq.size() && p2 < yseq.size()){
| ~~~^~~~~~~~~~~~~
potion.cpp:91:30: warning: 'slot' may be used uninitialized in this function [-Wmaybe-uninitialized]
91 | while (p1 != cj::big[slot][x].size() || p2 != cj::small[slot][x].size()){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2496 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2648 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2648 KB |
Output is correct |
| 4 |
Correct |
91 ms |
159752 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
347 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
307 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
130 ms |
67016 KB |
Output is correct |
| 2 |
Correct |
84 ms |
49956 KB |
Output is correct |
| 3 |
Correct |
124 ms |
49824 KB |
Output is correct |
| 4 |
Correct |
230 ms |
62340 KB |
Output is correct |
| 5 |
Correct |
226 ms |
65080 KB |
Output is correct |
| 6 |
Correct |
88 ms |
12880 KB |
Output is correct |
| 7 |
Correct |
217 ms |
51932 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2496 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2648 KB |
Output is correct |
| 4 |
Correct |
3 ms |
2648 KB |
Output is correct |
| 5 |
Correct |
91 ms |
159752 KB |
Output is correct |
| 6 |
Runtime error |
347 ms |
262144 KB |
Execution killed with signal 9 |
| 7 |
Halted |
0 ms |
0 KB |
- |
