結果
問題 | No.694 square1001 and Permutation 3 |
ユーザー |
|
提出日時 | 2019-02-16 16:34:26 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,230 ms / 3,000 ms |
コード長 | 1,248 bytes |
コンパイル時間 | 778 ms |
コンパイル使用メモリ | 79,128 KB |
実行使用メモリ | 11,264 KB |
最終ジャッジ日時 | 2024-09-22 13:34:49 |
合計ジャッジ時間 | 10,552 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 13 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>using namespace std;typedef long long ll;struct BIT{private:vector<int> bit;int n;public:BIT(int arg){n = arg + 1;bit.resize(n, 0);}void add(int i, int x){while(i <= n){bit[i] += x;i += i & -i;}}ll sum(int i){ll ret = 0;while(i > 0){ret += bit[i];i -= i & -i;}return ret;}};int main(){int n;cin >> n;vector<int> v(n);for(int i = 0; i < n; i++) cin >> v[i];vector<int> cp = v;sort(cp.begin(), cp.end());vector<int> cp2 = cp;cp.erase(unique(cp.begin(), cp.end()), cp.end());auto pos = [&](int val) -> int{return lower_bound(cp.begin(), cp.end(), val)-cp.begin();};BIT bit(cp.size());ll ans = 0;for(int i = 0; i < n; i++){ans += i-bit.sum(pos(v[i])+1);bit.add(pos(v[i])+1, 1);}cout << ans << endl;for(int i = 0; i < n-1; i++){ans += -(lower_bound(cp2.begin(),cp2.end(),v[i])-cp2.begin()) + (cp2.end()-upper_bound(cp2.begin(),cp2.end(),v[i]));cout << ans << endl;}return 0;}