結果
問題 | No.404 部分門松列 |
ユーザー |
![]() |
提出日時 | 2017-04-21 10:44:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,006 ms / 2,000 ms |
コード長 | 2,281 bytes |
コンパイル時間 | 1,682 ms |
コンパイル使用メモリ | 180,700 KB |
実行使用メモリ | 80,504 KB |
最終ジャッジ日時 | 2024-06-28 17:25:41 |
合計ジャッジ時間 | 17,536 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 31 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define rep(i,a,b) for(int i=a;i<b;i++)#define def 0template<class V, int NV> struct SegTree {V comp(V l, V r) { return l + r; };vector<V> val; SegTree() { val = vector<V>(NV * 2, def); }V get(int l, int r) { //[l,r]if (l > r) return def;l += NV; r += NV + 1; V ret = def;while (l < r) { if (l & 1) ret = comp(ret, val[l++]); if (r & 1) ret = comp(ret, val[--r]); l /= 2; r /= 2; }return ret;}void update(int i, V v) { i += NV; val[i] = v; while (i>1) i >>= 1, val[i] = comp(val[i * 2], val[i * 2 + 1]); }void add(int i, V v) { update(i, val[i + NV] + v); }};//-----------------------------------------------------------------------------------int N, A[201010], Q, L[201010], H[201010];//-----------------------------------------------------------------------------------void zatsu() {map<int, int> m;rep(i, 0, N) m[A[i]] = 0;rep(i, 0, Q) m[L[i]] = 0;rep(i, 0, Q) m[H[i]] = 0;int idx = 0;for (auto p : m) m[p.first] = idx, idx++;rep(i, 0, N) A[i] = m[A[i]];rep(i, 0, Q) L[i] = m[L[i]];rep(i, 0, Q) H[i] = m[H[i]];}//-----------------------------------------------------------------------------------typedef long long ll;SegTree<int, 1 << 20> le, ri;SegTree<ll, 1 << 20> cnt, same;void count() {rep(i, 0, N) ri.add(A[i], 1);rep(i, 0, N) {ri.add(A[i], -1);same.update(A[i], 1LL * le.get(A[i], A[i]) * ri.get(A[i], A[i]));ll L, R, SAME, c;L = le.get(0, A[i] - 1);R = ri.get(0, A[i] - 1);SAME = same.get(0, A[i] - 1);c = L * R - SAME;L = le.get(A[i] + 1, (1 << 20) - 1);R = ri.get(A[i] + 1, (1 << 20) - 1);SAME = same.get(A[i] + 1, (1 << 20) - 1);c += L * R - SAME;cnt.add(A[i], c);le.add(A[i], 1);same.update(A[i], 1LL * le.get(A[i], A[i]) * ri.get(A[i], A[i]));}}//-----------------------------------------------------------------------------------int main() {cin >> N;rep(i, 0, N) scanf("%d", &A[i]);cin >> Q;rep(i, 0, Q) scanf("%d%d", &L[i], &H[i]);zatsu();count();rep(i, 0, Q) printf("%lld\n", cnt.get(L[i], H[i]));}