結果
問題 | No.694 square1001 and Permutation 3 |
ユーザー |
![]() |
提出日時 | 2018-06-08 22:43:35 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,819 ms / 3,000 ms |
コード長 | 3,378 bytes |
コンパイル時間 | 1,924 ms |
コンパイル使用メモリ | 182,508 KB |
実行使用メモリ | 40,308 KB |
最終ジャッジ日時 | 2024-06-30 10:52:32 |
合計ジャッジ時間 | 12,263 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 13 |
ソースコード
#include "bits/stdc++.h"using namespace std;#define DEBUG(x) cout<<#x<<": "<<x<<endl;#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endltypedef long long ll;#define vi vector<int>#define vl vector<ll>#define vii vector< vector<int> >#define vll vector< vector<ll> >#define vs vector<string>#define pii pair<int,int>#define pis pair<int,string>#define psi pair<string,int>#define pll pair<ll,ll>template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }#define fi first#define se second#define rep(i,n) for(ll i=0;i<(ll)(n);i++)#define rep1(i,n) for(ll i=1;i<=(ll)(n);i++)#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)#define rrep1(i,n) for(ll i=(ll)(n);i>0;i--)#define REP(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)#define in(x, a, b) (a <= x && x < b)#define all(v) v.begin(),v.end()#define UNIQUE(v) v.erase(unique(all(v)), v.end())template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }const ll inf = 1000000001;const ll INF = 2e18;const ll MOD = 1000000007;const double pi = 3.14159265358979323846;#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;int dx[4] = { 1,0, -1,0 }, dy[4] = { 0,1,0,-1 };int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };#define fio() cin.tie(0); ios::sync_with_stdio(false);class Bit {public:int n;vl bit; // 1-indexBit(int _n) { n = _n; bit.resize(n); }// [0, i)の和ll sum(int i) {ll s = 0;while (i > 0) {s += bit[i - 1];i -= i & -i;}return s;}//iは0-indexvoid add(int i, ll x) {i++;while (i <= n) {bit[i - 1] += x;i += i & -i;}}// bitに入ってる中でx番目に小さい数を求める// 1番小さい数はx = 1;// bitに3を入れる→add(3, 1), 3を出す→add(3, -1)// return == nの場合x個も入っていないll min_xth(int x) {int left = -1, right = n;while (left + 1 < right) {int mid = (left + right) / 2;int temp = sum(mid + 1);if (temp < x) {left = mid;}else {right = mid;}}return right;}// 0,1,...,n - 1を並び替えた順列をバブルソートで// 順番通りにするための交換回数ll bubble(vi p) {int n = p.size();ll ans = 0;for (int j = 0; j < n; j++) {ans += (j - sum(p[j] + 1));add(p[j], 1);}return ans;}};int main() {int n;cin >> n;vi a(n);rep(i, n) {cin >> a[i];}vi b = a;sort(all(b));map<int, int> mp;int cnt = 0;rep(i, n) {if (mp[b[i]] == 0) {mp[b[i]] = ++cnt;}}vi low(cnt), high(cnt);int i = 0;while (i < n) {low[mp[b[i]] - 1] = i;int j = i;while (j < n && b[j] == b[i]) {j++;}high[mp[b[i]] - 1] = n - j;i = j;}rep(i, n) {a[i] = mp[a[i]] - 1;}Bit bit(cnt);ll res = bit.bubble(a);rep(i, n) {cout << res << endl;res = res - low[a[i]] + high[a[i]];;}}