結果
問題 | No.694 square1001 and Permutation 3 |
ユーザー |
![]() |
提出日時 | 2018-06-08 23:34:18 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,088 ms / 3,000 ms |
コード長 | 1,401 bytes |
コンパイル時間 | 1,744 ms |
コンパイル使用メモリ | 178,932 KB |
実行使用メモリ | 62,472 KB |
最終ジャッジ日時 | 2024-06-30 11:10:33 |
合計ジャッジ時間 | 13,407 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 13 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)#define rep(i,n) REP(i,0,n)#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)#define ALLOF(c) (c).begin(), (c).end()typedef long long ll;typedef unsigned long long ull;struct FenwickTree{static const int SIZE = 1<<21;int n;vector<int> tree;public:FenwickTree(int n_):tree(SIZE+1){n = n_;for(int i=0; i<n+1; i++) tree[i] = 0;}void add(int i, int value){for(; i<n; i|=i+1) tree[i] += value;}int sum(int i){int s = 0;for(; i>=0; i=(i&i+1)-1) s += tree[i];return s;}};int main(){int N;cin >> N;vector<int> A;map<int,int> mm, mp;rep(i,N){int a;cin >> a;A.push_back(a);if(mm.count(a) == 0){mm[a] = 1;}}int cnt = 0;FOR(it,mm){mp[it->first] = cnt++;}vector<int> B;rep(i,N){B.push_back(mp[A[i]]);}FenwickTree ft(N+10);ll sum = N * (ll)(N-1) / 2LL;ll ret = 0;rep(j,N){int tmp = ft.sum(B[j]);ret -= tmp;ft.add(B[j], 1);}cout << sum + ret << endl;rep(j,N-1){ft.add(B[j], -1);ll tmp1 = ft.sum(B[j]);ll tmp2 = ft.sum(N+5) - ft.sum(B[j]-1);//cout << tmp2 << " " << tmp1 << endl;ret += tmp2 - tmp1;cout << sum + ret << endl;ft.add(B[j], 1);}return 0;}