結果

問題 No.2873 Kendall's Tau
ユーザー lmorilmori
提出日時 2024-10-15 02:11:12
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 13,580 bytes
コンパイル時間 7,333 ms
コンパイル使用メモリ 312,772 KB
実行使用メモリ 70,400 KB
最終ジャッジ日時 2024-10-15 02:11:46
合計ジャッジ時間 32,971 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 13 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using ull = unsigned long long;
using ld = long double;
using int128 = __int128_t;
#define all(x) (x).begin(), (x).end()
#define EPS 1e-8
#define uniqv(v) v.erase(unique(all(v)), v.end())
#define OVERLOAD_REP(_1, _2, _3, name, ...) name
#define REP1(i, n) for (auto i = std::decay_t<decltype(n)>{}; (i) != (n); ++(i))
#define REP2(i, l, r) for (auto i = (l); (i) != (r); ++(i))
#define rep(...) OVERLOAD_REP(__VA_ARGS__, REP2, REP1)(__VA_ARGS__)
#define log(x) cout << x << endl
#define logfixed(x) cout << fixed << setprecision(15) << x << endl;
#define logy(bool) \
if (bool) { \
cout << "Yes" << endl; \
} else { \
cout << "No" << endl; \
}
ostream &operator<<(ostream &dest, __int128_t value) {
ostream::sentry s(dest);
if (s) {
__uint128_t tmp = value < 0 ? -value : value;
char buffer[128];
char *d = end(buffer);
do {
--d;
*d = "0123456789"[tmp % 10];
tmp /= 10;
} while (tmp != 0);
if (value < 0) {
--d;
*d = '-';
}
int len = end(buffer) - d;
if (dest.rdbuf()->sputn(d, len) != len) {
dest.setstate(ios_base::badbit);
}
}
return dest;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
for (int i = 0; i < (int)v.size(); i++) {
os << v[i] << (i + 1 != (int)v.size() ? " " : "");
}
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &set_var) {
for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
os << *itr;
++itr;
if (itr != set_var.end()) os << " ";
itr--;
}
return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &map_var) {
for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
os << itr->first << " -> " << itr->second << "\n";
}
return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &pair_var) {
os << "(" << pair_var.first << ", " << pair_var.second << ")";
return os;
}
void out() { cout << '\n'; }
template <class T, class... Ts>
void out(const T &a, const Ts &...b) {
cout << a;
(cout << ... << (cout << ' ', b));
cout << '\n';
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
for (T &in : v) is >> in;
return is;
}
inline void in(void) { return; }
template <typename First, typename... Rest>
void in(First &first, Rest &...rest) {
cin >> first;
in(rest...);
return;
}
template <typename T>
bool chmax(T &a, const T &b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <typename T>
bool chmin(T &a, const T &b) {
if (a > b) {
a = b;
return true;
}
return false;
}
vector<lint> dx8 = {1, 1, 0, -1, -1, -1, 0, 1};
vector<lint> dy8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<lint> dx4 = {1, 0, -1, 0};
vector<lint> dy4 = {0, 1, 0, -1};
#pragma endregion
#line 2 "data-structure/wavelet-matrix/WaveletMatrixRectangle.hpp"
class BitVector {
private:
unsigned n, cur, p;
vector<unsigned> acc, bit;
vector<unsigned long long> sum, srsum;
public:
BitVector() {
}
BitVector(vector<bool> &b, vector<unsigned> &v) {
cur = 0;
n = b.size();
acc.resize(n / 32 + 2, 0);
bit.resize(n / 32 + 2, 0);
sum.resize(n + 1, 0);
srsum.resize(n + 1, 0);
for (int i = 0; i < n; i++) {
p = i % 32;
if (p == 0) {
cur++;
acc[cur] = acc[cur - 1];
}
sum[i + 1] = sum[i] + v[i];
if (b[i]) {
acc[cur] += int(b[i]);
bit[cur - 1] |= (1U << (32 - p - 1));
}
}
}
inline void srsum_set(const vector<unsigned> &v) {
for (int i = 0; i < n; i++) {
srsum[i + 1] = srsum[i] + v[i];
}
}
inline unsigned rank(unsigned k) {
if (!(k & 31)) return acc[k / 32];
return acc[k / 32] + __builtin_popcount(bit[k / 32] >> (32 - (k & 31)));
}
inline unsigned long long rank_sum(unsigned k) {
return sum[k];
}
inline unsigned long long rank_srsum(unsigned k) {
return srsum[k];
}
inline bool access(unsigned k) {
return (rank(k + 1) - rank(k)) == 1;
}
};
class WaveletMatrix {
private:
unsigned n;
unsigned bitsize;
vector<BitVector> b;
vector<BitVector> cnt;
vector<unsigned> zero, zero2;
vector<int> stInd, prev;
vector<unsigned> prev_i;
vector<int> px;
vector<unsigned> compressed;
vector<int> cmp;
// prev_i[l,r) k
unsigned rank_less_prev(unsigned l, unsigned r, unsigned k) {
unsigned less = 0;
for (unsigned i = 0; i < bitsize and l < r; i++) {
const unsigned rank1_l = cnt[i].rank(l);
const unsigned rank1_r = cnt[i].rank(r);
const unsigned rank0_l = l - rank1_l;
const unsigned rank0_r = r - rank1_r;
if (k & (1U << (bitsize - i - 1))) {
less += (rank0_r - rank0_l);
l = zero2[i] + rank1_l;
r = zero2[i] + rank1_r;
} else {
l = rank0_l;
r = rank0_r;
}
}
return less;
}
inline unsigned compress(int x) {
return distance(cmp.begin(), lower_bound(cmp.begin(), cmp.end(), x));
}
public:
//
WaveletMatrix() {}
WaveletMatrix(vector<int> x, vector<int> y) {
n = x.size();
px.resize(n);
vector<tuple<int, int>> v(n);
for (int i = 0; i < n; i++) {
v[i] = {x[i], y[i]};
}
sort(v.begin(), v.end());
for (int i = 0; i < n; i++) {
px[i] = get<0>(v[i]);
y[i] = get<1>(v[i]);
}
cmp.resize(y.size());
cmp = y;
sort(cmp.begin(), cmp.end());
cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
compressed.resize(n);
vector<unsigned> tmp(n), tmpc(n);
unsigned size_mx = y.size();
for (unsigned i = 0; i < n; i++) {
compressed[i] = distance(cmp.begin(), lower_bound(cmp.begin(), cmp.end(), y[i]));
}
stInd.resize(cmp.size() + 1, -1);
bitsize = bit_width(size_mx);
b.resize(bitsize);
zero.resize(bitsize, 0);
vector<bool> bit(n, 0);
for (unsigned i = 0; i < bitsize; i++) {
for (unsigned j = 0; j < n; j++) {
bit[j] = compressed[j] & (1U << (bitsize - i - 1));
zero[i] += unsigned(!bit[j]);
tmpc[j] = compressed[j];
}
b[i] = BitVector(bit, compressed);
int cur = 0;
for (unsigned j = 0; j < n; j++) {
if (!bit[j]) {
compressed[cur] = tmpc[j];
cur++;
}
}
for (unsigned j = 0; j < n; j++) {
if (bit[j]) {
compressed[cur] = tmpc[j];
cur++;
}
}
}
for (unsigned i = 0; i < n; i++) {
if (stInd[compressed[i]] == -1) {
stInd[compressed[i]] = i;
}
}
}
// get v[k]
unsigned access(unsigned k) {
unsigned res = 0;
unsigned cur = k;
for (unsigned i = 0; i < bitsize; i++) {
if (b[i].access(cur)) {
res |= (1U << (bitsize - i - 1));
cur = zero[i] + b[i].rank(cur);
} else {
cur -= b[i].rank(cur);
}
}
return cmp[res];
}
// v[0,k) c
unsigned rank(unsigned k, unsigned c) {
c = compress(c);
unsigned cur = k;
if (stInd[c] == -1) {
return 0;
}
for (unsigned i = 0; i < bitsize; i++) {
if (c & (1U << (bitsize - i - 1))) {
cur = zero[i] + b[i].rank(cur);
} else {
cur -= b[i].rank(cur);
}
}
return cur - stInd[c];
}
// v[l,r) {kkk}
vector<unsigned> rank_less_more(unsigned l, unsigned r, unsigned k) {
unsigned range = r - l;
unsigned less = 0;
unsigned more = 0;
for (unsigned i = 0; i < bitsize and l < r; i++) {
const unsigned rank1_l = b[i].rank(l);
const unsigned rank1_r = b[i].rank(r);
const unsigned rank0_l = l - rank1_l;
const unsigned rank0_r = r - rank1_r;
if (k & (1U << (bitsize - i - 1))) {
less += (rank0_r - rank0_l);
l = zero[i] + rank1_l;
r = zero[i] + rank1_r;
} else {
more += (rank1_r - rank1_l);
l = rank0_l;
r = rank0_r;
}
}
unsigned rank = range - more - less;
return {less, rank, more};
}
// v[l,r) k
unsigned long long rank_less_sum(unsigned l, unsigned r, unsigned k) {
unsigned long long less_sum = 0;
for (unsigned i = 0; i < bitsize and l < r; i++) {
const unsigned rank1_l = b[i].rank(l);
const unsigned rank1_r = b[i].rank(r);
const unsigned rank0_l = l - rank1_l;
const unsigned rank0_r = r - rank1_r;
if (k & (1U << (bitsize - i - 1))) {
less_sum += b[i].rank_srsum(rank0_r) - b[i].rank_srsum(rank0_l);
l = zero[i] + rank1_l;
r = zero[i] + rank1_r;
} else {
l = rank0_l;
r = rank0_r;
}
}
return less_sum;
}
// v[l,r) k
unsigned rank_less(unsigned l, unsigned r, unsigned k) {
unsigned less = 0;
for (unsigned i = 0; i < bitsize and l < r; i++) {
const unsigned rank1_l = b[i].rank(l);
const unsigned rank1_r = b[i].rank(r);
const unsigned rank0_l = l - rank1_l;
const unsigned rank0_r = r - rank1_r;
if (k & (1U << (bitsize - i - 1))) {
less += (rank0_r - rank0_l);
l = zero[i] + rank1_l;
r = zero[i] + rank1_r;
} else {
l = rank0_l;
r = rank0_r;
}
}
return less;
}
// v[l,r) k-1
unsigned kth_smallest(unsigned l, unsigned r, unsigned k) {
unsigned res = 0;
for (unsigned i = 0; i < bitsize; i++) {
unsigned num1 = b[i].rank(r) - b[i].rank(l);
unsigned num0 = r - l - num1;
if (num0 < k) {
res |= (1ULL << (bitsize - i - 1));
l = zero[i] + b[i].rank(l);
r = zero[i] + b[i].rank(r);
k -= num0;
} else {
l -= b[i].rank(l);
r -= b[i].rank(r);
}
}
return cmp[res];
}
// v[l,r]k
unsigned long long kth_sum(unsigned l, unsigned r, unsigned k) {
unsigned long long res = 0;
unsigned val = 0;
for (unsigned i = 0; i < bitsize; i++) {
const unsigned rank1_l = b[i].rank(l);
const unsigned rank1_r = b[i].rank(r);
const unsigned rank0_l = l - rank1_l;
const unsigned rank0_r = r - rank1_r;
const unsigned num1 = rank1_r - rank1_l;
const unsigned num0 = rank0_r - rank0_l;
if (num0 < k) {
val |= (1ULL << (bitsize - i - 1));
res += b[i].rank_srsum(rank0_r) - b[i].rank_srsum(rank0_l);
l = zero[i] + rank1_l;
r = zero[i] + rank1_r;
k -= num0;
} else {
l = rank0_l;
r = rank0_r;
}
}
res += uint64_t(cmp[val]) * uint64_t(k);
return res;
}
// v[l,r) [mink,maxk)
unsigned range_freq(unsigned l, unsigned r, int mink, int maxk) {
mink = compress(mink);
maxk = compress(maxk);
return rank_less(l, r, maxk) - rank_less(l, r, mink);
}
// v[l,r) [mink,maxk)
unsigned long long range_sum(unsigned l, unsigned r, unsigned mink, unsigned maxk) {
mink = compress(mink);
maxk = compress(maxk);
return rank_less_sum(l, r, maxk) - rank_less_sum(l, r, mink);
}
// x[l,r) y[d,u)
unsigned rectangle_freq(int l, int r, int d, int u) {
l = distance(px.begin(), lower_bound(px.begin(), px.end(), l));
r = distance(px.begin(), lower_bound(px.begin(), px.end(), r));
return range_freq(l, r, d, u);
}
// x[l,r) y[d,u)
unsigned long long rectangle_sum(unsigned l, unsigned r, unsigned d, unsigned u) {
l = distance(px.begin(), lower_bound(px.begin(), px.end(), l));
r = distance(px.begin(), lower_bound(px.begin(), px.end(), r));
return range_sum(l, r, d, u);
}
// v[l,r)
unsigned range_count(unsigned l, unsigned r) {
return rank_less_prev(l, r, l + 1);
}
// v[l,r)val
unsigned prev_value(unsigned l, unsigned r, unsigned val) {
int num = range_freq(l, r, 0, val);
if (num == 0) {
return UINT32_MAX;
} else {
return kth_smallest(l, r, num);
}
}
// v[l,r)val
unsigned next_value(unsigned l, unsigned r, unsigned val) {
int num = range_freq(l, r, 0, val);
if (num == r - l) {
return UINT32_MAX;
} else {
return kth_smallest(l, r, num + 1);
}
}
};
int main() {
int INF = 1e9 + 10;
cin.tie(0);
ios::sync_with_stdio(false);
int n;
in(n);
vector<int> x(n), y(n), o(n);
rep(i, n) {
in(x[i], y[i]);
}
WaveletMatrix w(x, y);
lint p, q, r, s;
p = q = r = s = 0;
rep(i, n) {
int cx = x[i];
int cy = y[i];
p += w.rectangle_freq(cx + 1, INF, cy + 1, INF) + w.rectangle_freq(-INF, cx, -INF, cy);
q += w.rectangle_freq(-INF, cx, cy + 1, INF) + w.rectangle_freq(cx + 1, INF, -INF, cy);
r += w.rectangle_freq(-INF, cx, -INF, INF) + w.rectangle_freq(cx + 1, INF, -INF, INF);
s += w.rectangle_freq(-INF, INF, -INF, cy) + w.rectangle_freq(-INF, INF, cy + 1, INF);
}
p /= 2;
q /= 2;
r /= 2;
s /= 2;
logfixed((p - q) / sqrtl(r * s));
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0