結果
問題 | No.694 square1001 and Permutation 3 |
ユーザー | tetsu |
提出日時 | 2018-06-08 23:32:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,112 bytes |
コンパイル時間 | 1,859 ms |
コンパイル使用メモリ | 182,544 KB |
実行使用メモリ | 116,760 KB |
最終ジャッジ日時 | 2024-06-30 11:11:40 |
合計ジャッジ時間 | 18,595 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 3 ms
5,376 KB |
testcase_04 | AC | 3 ms
5,376 KB |
testcase_05 | AC | 3 ms
5,376 KB |
testcase_06 | AC | 3 ms
5,376 KB |
testcase_07 | AC | 1,097 ms
22,912 KB |
testcase_08 | AC | 2,295 ms
41,660 KB |
testcase_09 | TLE | - |
testcase_10 | AC | 908 ms
22,908 KB |
testcase_11 | TLE | - |
testcase_12 | TLE | - |
testcase_13 | AC | 2 ms
5,376 KB |
ソースコード
#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() {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;}