結果
問題 | No.742 にゃんにゃんにゃん 猫の挨拶 |
ユーザー | sima.tetteke |
提出日時 | 2019-12-13 20:14:56 |
言語 | C++11 (gcc 11.4.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,872 bytes |
コンパイル時間 | 1,403 ms |
コンパイル使用メモリ | 163,020 KB |
実行使用メモリ | 13,824 KB |
最終ジャッジ日時 | 2024-06-27 14:33:42 |
合計ジャッジ時間 | 8,938 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | -- | - |
testcase_02 | -- | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
ソースコード
#include "bits/stdc++.h" using namespace std; typedef long long int ll; typedef pair<ll, ll > pi; typedef pair<pair<ll, ll >, ll > pii; vector<ll > vec; vector<vector<ll > > vec2; ll MOD = 1000000007; ll INF = 11451419194545; ll N; //Binary Indexed Treeの本体 vector<ll > bit; //要素の追加 void add(ll a, ll w){ //区間の長さと現在追加しようとしている値の添字を足すと求めることができる //区間の長さは区間番号を2進数にした時,最も下位にある立ったビットで分かる //x & -xで最も下位の立ったbitが分かる for(ll i = a; i <= N; i += i & -i){ bit[i] += w; } } //区間1~aの和の計算 ll intervalSum(ll a){ //次にどこを足せばよいかは区間番号からその区間番号の長さを引くと求まる ll ret = 0; for(ll i = a; i > 0; i -= i & -i){ ret += bit[i]; } return ret; } ll invNum(vector<ll > num){ ll ans = 0; for(ll i = 0; i < N; i++){ ans += num[i] - intervalSum(num[i]); add(num[i], 1); } return ans; } int main() { ll q; cin >> N >> q; bit.assign(N+1, 0); //立っているビットが常に1つある状態にしたいので添字は1からスタート /* for(ll i = 1; i <= N; i++){ ll t = 0; cin >> t; add(i, t); } */ /*クエリの処理 vector<ll > ans; for(ll i = 0; i < q; i++){ ll com; cin >> com; ll x, y; cin >> x >> y; if(com == 0){ add(x, y); }else{ ans.push_back(intervalSum(y) - intervalSum(x-1)); //cout << intervalSum(y) - intervalSum(x-1) << endl; } } */ //転倒数 vector<ll > num(N, 0); for(ll i = 0; i < N; i++){ cin >> num[i]; } cout << invNum(num) << endl; }