結果
問題 | No.742 にゃんにゃんにゃん 猫の挨拶 |
ユーザー |
![]() |
提出日時 | 2018-02-26 16:14:28 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 17 ms / 2,500 ms |
コード長 | 1,116 bytes |
コンパイル時間 | 2,462 ms |
コンパイル使用メモリ | 164,196 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-12 13:54:02 |
合計ジャッジ時間 | 2,156 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)using ll = long long; using vll = vector<ll>;// Point Assign Range Sumtemplate<class T>struct SegmentTreeSum {int n; vector<T> dat;SegmentTreeSum(int n_ = 0) : n(n_){for(n = 1; n < n_; n <<= 1);dat.resize(n*2, 0);}T sum(int v, int w, int l, int r){if(r <= l || w == 0) return 0;if(r - l == w) return dat[v]; // assert(l == 0 && r == w);int m = w/2;return (sum(v*2, m, l, min(r,m)) + sum(v*2+1, m, max(0,l-m), r-m));}void assign(int i, const T &x){dat[i+=n] = x;for(; i!=1; i/=2) dat[i/2] = dat[i] + dat[i^1];}T sum(int l, int r){ return sum(1,n,l,r); }size_t size() const { return n; }T operator [] (const int &idx) { return sum(idx, idx + 1); }};int main(void) {ll n; cin >> n;SegmentTreeSum<ll> st(n);ll ret = 0;rep(i, n) {ll x; cin >> x; x--;ret += st.sum(x, n);st.assign(x, 1);}cout << ret << endl;return 0;}