結果
問題 | No.742 にゃんにゃんにゃん 猫の挨拶 |
ユーザー |
![]() |
提出日時 | 2019-08-27 09:36:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 11 ms / 2,500 ms |
コード長 | 1,439 bytes |
コンパイル時間 | 1,493 ms |
コンパイル使用メモリ | 170,140 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-14 04:18:12 |
合計ジャッジ時間 | 2,334 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include "bits/stdc++.h"#define ALL(obj) (obj).begin(),(obj).end()#define RALL(obj) (obj).rbegin(),(obj).rend()#define REP(i, n) for(int i = 0; i < (int)(n); i++)#define REPR(i, n) for(int i = (int)(n); i >= 0; i--)#define FOR(i,n,m) for(int i = (int)(n); i < int(m); i++)using namespace std;typedef long long ll;const int MOD = 1e9 + 7;const int INF = MOD - 1;const ll LLINF = 4e18;// 0-indexedとして使う// 実装は1-indexedtemplate< typename T >struct BinaryIndexedTree {vector< T > data;BinaryIndexedTree(int sz) {data.assign(++sz, 0);}// [0,k]T sum(int k) {T ret = 0;for (++k; k > 0; k -= k & -k) ret += data[k];return (ret);}// [left,right]T sum(int left, int right) {return sum(right) - sum(left - 1);}void add(int k, T x) {for (++k; k < data.size(); k += k & -k) data[k] += x;}void print() {cout << "[ ";for (int i = 1; i < data.size(); i++) {cout << data[i];if (i < data.size() - 1) cout << ", ";}cout << " ]";}};int main() {int n; cin >> n;BinaryIndexedTree< int > bit(n+1);vector<int> m(n);REP(i, n) {cin >> m[i];}int ans = 0;REP(i, n) {ans += i - bit.sum(m[i]);bit.add(m[i], 1);}//bit.print();cout << ans << endl;getchar(); getchar();}