結果

問題 No.742 にゃんにゃんにゃん 猫の挨拶
ユーザー xuzijian629xuzijian629
提出日時 2018-10-09 05:04:13
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 125 ms / 2,500 ms
コード長 2,331 bytes
コンパイル時間 2,151 ms
コンパイル使用メモリ 172,964 KB
実行使用メモリ 33,280 KB
最終ジャッジ日時 2024-10-12 16:16:00
合計ジャッジ時間 3,191 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using vi = vector<i64>;
using vvi = vector<vi>;
class RangeCount {
const int ST_SIZE = (1 << 20) - 1;
int n;
vi data;
vvi segtree;
void init(int k, int l, int r) {
if (r - l == 1) {
segtree[k].push_back(data[l]);
} else {
int lch = k * 2 + 1;
int rch = k * 2 + 2;
init(lch, l, (l + r) / 2);
init(rch, (l + r) / 2, r);
segtree[k].resize(r - l);
merge(segtree[lch].begin(), segtree[lch].end(), segtree[rch].begin(), segtree[rch].end(), segtree[k].begin());
}
}
// number of x in [i, j)
int query(int i, int j, i64 x, int k, int l, int r) {
if (j <= l || r <= i) {
return 0;
}
if (i <= l && r <= j) {
return upper_bound(segtree[k].begin(), segtree[k].end(), x) - segtree[k].begin();
}
int lc = query(i, j, x, k * 2 + 1, l, (l + r) / 2);
int rc = query(i, j, x, k * 2 + 2, (l + r) / 2, r);
return lc + rc;
}
public:
RangeCount(vi v) {
n = v.size();
data = vi(v);
segtree = vvi(ST_SIZE);
init(0, 0, n);
}
int exact(int i, int j, i64 x) {
return query(i, j, x, 0, 0, n) - query(i, j, x - 1, 0, 0, n);
}
int le(int i, int j, i64 x) {
return query(i, j, x, 0, 0, n);
}
int lt(int i, int j, i64 x) {
return query(i, j, x - 1, 0, 0, n);
}
int ge(int i, int j, i64 x) {
return query(i, j, 1e18, 0, 0, n) - query(i, j, x - 1, 0, 0, n);
}
int gt(int i, int j, i64 x) {
return query(i, j, 1e18, 0, 0, n) - query(i, j, x, 0, 0, n);
}
};
int main() {
int n;
cin >> n;
vi vs(n);
i64 ans = 0;
for (int i = 0; i < n; i++) {
cin >> vs[i];
vs[i]--;
}
RangeCount cnt(vs);
for (int i = 0; i < n; i++) {
if (vs[i] >= i) {
ans += cnt.gt(0, i, vs[i]);
ans += cnt.le(i, vs[i] + 1, vs[i]) - 1;
ans += cnt.le(vs[i] + 1, n + 1, vs[i]);
} else {
ans += cnt.ge(0, vs[i], vs[i]);
ans += cnt.ge(vs[i], i + 1, vs[i]) - 1;
ans += cnt.le(i + 1, n + 1, vs[i]);
}
}
cout << ans / 2 << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0