結果
問題 | No.694 square1001 and Permutation 3 |
ユーザー |
|
提出日時 | 2018-09-27 18:01:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,860 ms / 3,000 ms |
コード長 | 1,049 bytes |
コンパイル時間 | 1,952 ms |
コンパイル使用メモリ | 207,256 KB |
最終ジャッジ日時 | 2025-01-06 13:49:04 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 13 |
ソースコード
#include <bits/stdc++.h>using namespace std;struct Ftree {vector<int> dat;Ftree(int n) : dat(n, 0) {}void add(int x) {for (int i = x; i < dat.size(); i += i & -i) ++dat[i];}int sum(int x) {int res = 0;for (int i = x; i; i -= i & -i) res += dat[i];return res;}};struct MapZstar {vector<int> dsc;map<int, int> mp;MapZstar(const vector<int> &d) {dsc = d;sort(dsc.begin(), dsc.end());dsc.erase(unique(dsc.begin(), dsc.end()), dsc.end());for (int i = 0; i < dsc.size(); ++i) mp[dsc[i]] = i;}};signed main() {ios::sync_with_stdio(false);int N;cin >> N;vector<int> A(N);for (int i = 0; i < N; ++i) cin >> A[i];MapZstar mz(A);Ftree f(mz.dsc.size() + 1);int64_t cur = 0;for (int i = 0; i < N; ++i) {cur += f.sum(f.dat.size() - 1) - f.sum(mz.mp[A[i]] + 1);f.add(mz.mp[A[i]] + 1);}for (int i = 0; i < N; ++i) {cout << cur << endl;cur += f.sum(f.dat.size() - 1) - f.sum(mz.mp[A[i]] + 1);cur -= f.sum(mz.mp[A[i]]);}}