結果
問題 | No.694 square1001 and Permutation 3 |
ユーザー |
|
提出日時 | 2018-06-08 23:48:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,157 bytes |
コンパイル時間 | 1,797 ms |
コンパイル使用メモリ | 182,912 KB |
実行使用メモリ | 116,536 KB |
最終ジャッジ日時 | 2024-06-30 11:17:32 |
合計ジャッジ時間 | 18,461 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 TLE * 3 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define ll long long#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)ll tentou(vector<ll> v) {if(v.size()<=1) {return 0;}ll n = v.size();vector<ll> h1;vector<ll> h2;for(int i=0; i<n/2; i++) {h1.push_back(v[i]);}for(int i=n/2; i<n; i++) {h2.push_back(v[i]);}ll t1 = tentou(h1);ll t2 = tentou(h2);sort(h1.begin(), h1.end());sort(h2.begin(), h2.end());ll idx=0;ll ans = t1+t2;for(auto x : h1) {while(idx<h2.size()&&h2[idx]<x) idx++;ans+=idx;}return ans;}int main() {cin.tie(0);ios::sync_with_stdio(false);int n;cin >> n;vector<ll> v(n);map<ll,ll> m;rep(i, n) {cin >> v[i];if(m.find(v[i])!=m.end()) {m[v[i]]++;} else {m[v[i]]=1;}}map<ll,ll> bigger;map<ll,ll> smaller;{ll acc = 0;for(auto itr : m) {smaller[itr.first] = acc;bigger[itr.first] = n-acc-itr.second;acc+=itr.second;}}ll cnt = tentou(v);cout << cnt << endl;rep(i, n-1) {cnt-=smaller[v[i]];cnt+=bigger[v[i]];cout << cnt<<endl;}return 0;}