#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<vector<int>> slots;
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];
}
bool C(int A, int B){
if (h[A] == h[B]){
return A < B;
}
return h[A] < h[B];
}
bool Comp2(pair<int,int> A, pair<int,int> B){
return A.second < B.second;
}
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();
}
}
template<class _T>
inline void copy(vector<_T> &from, vector<_T> &to){
to.clear();
for (int i : from){
to.push_back(i);
}
}
inline void clean(vector<int> &V){
vector<int> p;
copy<int>(V, p);
sort(p.begin(), p.end(), C);
V.clear();
for (int i : p){
push(V, i);
}
return;
}
}
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));
cj::big = vector<vector<vector<int>>>(cj::n, vector<vector<int>>(0));
cj::small = vector<vector<vector<pair<int,int>>>>(cj::n, vector<vector<pair<int,int>>>(0));
cj::slots = vector<vector<int>>(cj::n, vector<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});
}
for (int i = 0; i < cj::n; i++){
sort(cj::graph[i].begin(), cj::graph[i].end(), cj::Comp2);
}
for (int i = 0; i < cj::n; i++){
cj::big[i].push_back({});
cj::small[i].push_back({});
cj::slots[i].push_back(1e9);
for (int j = 0; j < cj::graph[i].size(); j++){
if (cj::small[i].size() == cj::sqrtu){
cj::big[i].push_back({});
cj::copy<int>(*(cj::big[i].end() - 2), cj::big[i].back());
for (pair<int,int> p : cj::small[i].back()){
cj::big[i].back().push_back(p.first);
}
cj::clean(cj::big[i].back());
cj::small[i].push_back({});
cj::slots[i].push_back(1e9);
}
cj::small[i].back().push_back(cj::graph[i][j]);
if (cj::slots[i].back() == 1e9){
cj::slots[i].back() = cj::small[i].back()[0].second;
}
}
for (int j = 0; j < cj::small[i].size(); j++){
sort(cj::small[i][j].begin(), cj::small[i][j].end(), cj::Comp);
}
}
}
inline void genseq(int x, int v, vector<int> &ret){
int slot;
vector<int> s;
ret.clear();
for (int i = cj::slots[x].size() - 1; i >= 0; i--){
if (cj::slots[x][i] <= v){
slot = i;
break;
}
}
for (pair<int,int> i : cj::small[x][slot]){
if (i.second <= v){
cj::push(s, i.first);
}
}
int p1 = 0, p2 = 0;
while (p1 < s.size() || p2 < cj::big[x][slot].size()){
if (p1 == s.size()){
cj::push(ret, cj::big[x][slot][p2]);
p2++;
}
else if (p2 == cj::big[x][slot].size()){
cj::push(ret, s[p1]);
p1++;
}
else if (cj::h[s[p1]] > cj::h[cj::big[x][slot][p2]]){
cj::push(ret, cj::big[x][slot][p2]);
p2++;
}
else {
cj::push(ret, s[p1]);
p1++;
}
}
}
int question(int x, int y, int v) {
v--;
if (v == -1) return 1e9;
vector<int> xseq, yseq;
genseq(x, v, xseq);
genseq(y, v, yseq);
int p1 = 0, p2 = 0, output = 1e9;
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[xseq[p2]]){
p1++;
}
else {
p2++;
}
}
return output;
}
Compilation message
potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:90:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for (int j = 0; j < cj::graph[i].size(); j++){
| ~~^~~~~~~~~~~~~~~~~~~~~
potion.cpp:91:37: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
91 | if (cj::small[i].size() == cj::sqrtu){
| ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
potion.cpp:106:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for (int j = 0; j < cj::small[i].size(); j++){
| ~~^~~~~~~~~~~~~~~~~~~~~
potion.cpp: In function 'void genseq(int, int, std::vector<int>&)':
potion.cpp:128:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | while (p1 < s.size() || p2 < cj::big[x][slot].size()){
| ~~~^~~~~~~~~~
potion.cpp:128:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | while (p1 < s.size() || p2 < cj::big[x][slot].size()){
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp:129:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | if (p1 == s.size()){
| ~~~^~~~~~~~~~~
potion.cpp:133:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | else if (p2 == cj::big[x][slot].size()){
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:155:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
155 | while (p1 < xseq.size() && p2 < yseq.size()){
| ~~~^~~~~~~~~~~~~
potion.cpp:155:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
155 | while (p1 < xseq.size() && p2 < yseq.size()){
| ~~~^~~~~~~~~~~~~
potion.cpp: In function 'void genseq(int, int, std::vector<int>&)':
potion.cpp:122:45: warning: 'slot' may be used uninitialized in this function [-Wmaybe-uninitialized]
122 | for (pair<int,int> i : cj::small[x][slot]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
732 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
125 ms |
69284 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
125 ms |
69304 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
3768 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
732 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
