結果
問題 | No.694 square1001 and Permutation 3 |
ユーザー |
![]() |
提出日時 | 2018-06-09 00:41:21 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 672 ms / 3,000 ms |
コード長 | 1,923 bytes |
コンパイル時間 | 1,551 ms |
コンパイル使用メモリ | 168,996 KB |
実行使用メモリ | 23,332 KB |
最終ジャッジ日時 | 2024-06-30 12:07:12 |
合計ジャッジ時間 | 6,849 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 13 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;#define rep(i,n) for(int i=0;i<(n);i++)#define reps(i,f,n) for(int i=(f);i<(n);i++)template <class T> //T : dat[]の中身の型class segtree{public:int n;T neutral;vector<T> dat;T func(T l, T r){ //区間をマージする関数return l + r;}segtree(int n_, T val): n(n_), neutral(val){ //n_:要素数 val:単位元n = 1;while(n < n_) n *= 2;dat.resize(n * 2, neutral); //初期値}void update(int k, T val){ // k番目の値(0-indexed)を val に変更for (dat[k += n] += val; k > 0; k >>= 1){ // kを含む区間のインデックスを下から順に列挙dat[k>>1] = func(dat[k], dat[k ^ 1]);}}T query(int l, int r){ //[l, r)の区間/* 可換出ない時危険 */T ret = neutral;for (l += n, r += n; l < r; l >>= 1, r >>= 1){if(l & 1) ret = func(ret, dat[l++]);if(r & 1) ret = func(ret, dat[--r]);}return ret;}};int main(int argc, char const *argv[]){int n; cin >> n;vector<int> _a(n), tmpa(n);rep(i, n) cin >> _a[i];rep(i, n) tmpa[i] = _a[i];sort(tmpa.begin(), tmpa.end());tmpa.erase(unique(tmpa.begin(), tmpa.end()), tmpa.end());vector<int> a(n), sorta(n);rep(i, n) a[i] = lower_bound(tmpa.begin(), tmpa.end(), _a[i]) - tmpa.begin() + 1;rep(i, n) sorta[i] = a[i];sort(sorta.begin(), sorta.end());// rep(i, n) printf("%d ", a[i]);// printf("\n");segtree<ll> seg(n + 10, 0);ll cnt0 = 0;rep(i, n) {cnt0 += seg.query(a[i] + 1, n + 1);seg.update(a[i], 1);}// printf("cnt0 %lld\n", cnt0);vector<ll> cnt(n);cnt[0] = cnt0;reps(i, 1, n) {int d1 = lower_bound(sorta.begin(), sorta.end(), a[i - 1]) - sorta.begin();int d2 = n - (upper_bound(sorta.begin(), sorta.end(), a[i - 1]) - sorta.begin());// printf("d1 %d d2 %d\n", d1, d2);cnt[i] = cnt[i - 1] - d1 + d2;}for(auto u : cnt) printf("%lld\n", u);return 0;}