結果
問題 | No.742 にゃんにゃんにゃん 猫の挨拶 |
ユーザー |
|
提出日時 | 2020-10-01 10:25:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 6 ms / 2,500 ms |
コード長 | 920 bytes |
コンパイル時間 | 2,435 ms |
コンパイル使用メモリ | 193,140 KB |
最終ジャッジ日時 | 2025-01-14 23:49:07 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define REP(i,n) for(int i=0; i<(int)(n); i++)template <typename T>class BIT {vector<T> bit;public:BIT() {}// manage data in [1, n]BIT(int n) : bit(n + 1) {}void init() {fill(bit.begin(), bit.end(), 0);}// return sum in [1, i]T sum(int i){T s = 0;while(i > 0){s += bit[i];i -= i & -i;}return s;}// return sum in [l, r]T sum(int l, int r) {return sum(r) - sum(l-1);}void add(int i, T x){while(i < (int)bit.size()){bit[i] += x;i += i & -i;}}};int main() {ios_base::sync_with_stdio(0);cin.tie(0);int n;cin >> n;int ret = 0;BIT<int> tree(30000);REP (i, n) {int m;cin >> m;tree.add(m, 1);if (m == 1)ret += i;elseret += i - tree.sum(m-1);}cout << ret << endl;return 0;}