結果
問題 | No.742 にゃんにゃんにゃん 猫の挨拶 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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;}