結果
問題 | No.404 部分門松列 |
ユーザー |
![]() |
提出日時 | 2017-02-18 17:52:32 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,454 ms / 2,000 ms |
コード長 | 2,398 bytes |
コンパイル時間 | 1,490 ms |
コンパイル使用メモリ | 94,428 KB |
実行使用メモリ | 29,312 KB |
最終ジャッジ日時 | 2024-06-28 17:18:44 |
合計ジャッジ時間 | 8,087 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 31 |
ソースコード
#include <iostream>#include <cassert>#include <algorithm>#include <vector>#include <map>using namespace std;struct BIT{vector<int64_t> bit;int64_t size;BIT(int64_t n){size=n;bit=vector<int64_t>(n+1);}//a[i]=xvoid add(int64_t i,int64_t x){i+=1;while(i<=size)bit[i]+=x,i+=i&-i;}int64_t get(int64_t i) {return sum(i + 1) - sum(i);}//a[k] (k<i)の和int64_t sum(int64_t i){int64_t s=0;while(i>0)s+=bit[i],i-=i&-i;return s;}};int N;vector<int64_t> a;vector<int64_t> ca;map<int64_t, int64_t> compress_table;map<int64_t, int64_t> answer_count;// aの値を圧縮するテーブルを作成するvoid init_compress_table() {ca = a;sort(ca.begin(), ca.end());ca.erase(unique(ca.begin(), ca.end()), ca.end());for(int i = 0; i < ca.size(); i++) {compress_table[ca[i]] = i;}}// aの値を圧縮するint compress(int64_t b) {assert(compress_table.count(b));return compress_table[b];}int main() {cin >> N;a.resize(N);for(auto &num: a) cin >> num;init_compress_table();BIT left(N + 1), right(N + 1);for(int i = 0; i < N; i++) {right.add(compress(a[i]), 1);}int64_t same = 0;for(int i = 0; i < N; i++) {int cpa = compress(a[i]);same -= left.get(cpa) * right.get(cpa);right.add(compress(a[i]), -1);same += left.get(cpa) * right.get(cpa);// 小さいものint64_t l_sum = left.sum(cpa);int64_t r_sum = right.sum(cpa);answer_count[a[i]] += l_sum * r_sum;// 大きいものl_sum = left.sum(N + 1) - left.sum(cpa + 1);r_sum = right.sum(N + 1) - right.sum(cpa + 1);answer_count[a[i]] += l_sum * r_sum;// 同じもの(後で引く)l_sum = left.get(cpa);r_sum = right.get(cpa);answer_count[a[i]] += l_sum * r_sum;// 左右が同じものを引くanswer_count[a[i]] -= same;same -= left.get(cpa) * right.get(cpa);left.add(compress(a[i]), 1);same += left.get(cpa) * right.get(cpa);}BIT answer(N + 1);for(auto t: answer_count) {answer.add(compress(t.first), t.second);}int64_t Q;cin >> Q;for(int i = 0; i < Q; i++) {int64_t L, H;cin >> L >> H;H ++;int64_t a = -answer.sum(lower_bound(ca.begin(), ca.end(), L) - ca.begin());a += answer.sum(lower_bound(ca.begin(), ca.end(), H) - ca.begin());cout << a << endl;}}