#include "treasure.h"
#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
const int maxn = 1e4 + 4;
const int inf = 5e8 + 1;
vector<int> encode(vector<pair<int, int>> P) {
int n = (int)P.size();
vector<int> res;
vector<int> tx, ty;
set<pair<int, int>> s;
for (int i = 0; i < (int)P.size(); ++i) {
ty.push_back(P[i].second);
res.push_back(P[i].first);
res.push_back(P[i].second + inf);
}
sort(ty.begin(), ty.end());
for (int i = 0; i < (int)ty.size(); ++i) {
s.insert(make_pair(ty[i], i));
}
sort(P.begin(), P.end());
int cur = inf * 2;
for (int i = 0; i < P.size(); ++i) {
auto it = s.lower_bound(make_pair(P[i].second, -1));
cur += it->second;
res.push_back(cur);
s.erase(it);
}
return res;
}
vector<pair<int, int>> decode(vector<int> S) {
vector<int> tx, ty;
vector<int> prf;
for (auto i : S) {
if (i < inf) {
tx.push_back(i);
} else if (i < inf * 2) {
ty.push_back(i - inf);
} else {
prf.push_back(i);
}
}
sort(tx.begin(), tx.end());
sort(ty.begin(), ty.end());
sort(prf.begin(), prf.end());
vector<pair<int, int>> res;
int prv = inf * 2;
for (int i = 0; i < (int)prf.size(); ++i) {
res.emplace_back(tx[i], ty[prf[i] - prv]);
prv = prf[i];
}
debug(res);
return res;
}
