結果
問題 | No.404 部分門松列 |
ユーザー | Kurl |
提出日時 | 2024-10-13 00:27:45 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,113 bytes |
コンパイル時間 | 1,993 ms |
コンパイル使用メモリ | 176,144 KB |
実行使用メモリ | 23,732 KB |
最終ジャッジ日時 | 2024-10-13 00:27:55 |
合計ジャッジ時間 | 9,085 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 6 ms
17,472 KB |
testcase_01 | AC | 6 ms
17,204 KB |
testcase_02 | WA | - |
testcase_03 | AC | 7 ms
17,336 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | AC | 86 ms
19,360 KB |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
ソースコード
# include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 200010; ll n, cnt, godamn, q; ll a[N], b[N]; ll lt[N], rt[N]; ll c[N]; vector <ll> G[N]; vector <ll> sum(N), ans(N); map <ll, ll> id; ll lowbit(ll x) {return x & (-x);} void add(ll x, ll ADD) { for (int i = x; i <= n; i += lowbit(i)) c[i] += ADD; } ll ask(ll x) { ll res; res = 0; for (int i = x; i; i -= lowbit(i)) res += c[i]; return res; } ll find(ll x, ll y) {return lower_bound(b, b + y, x) - b;} int main() { scanf("%lld", &n); for (int i = 0; i < n; i++) scanf("%lld", &a[i]), b[i] = a[i]; sort(b, b + n); cnt = unique(b, b + n) - b; for (int i = 0; i < n; i++) a[i] = find(a[i], n); for (int i = 0; i < n; i++) G[a[i]].push_back(i); // cout << cnt << endl; // cout<<"?1\n"; for (int i = 0; i < cnt; i++) { for (int j = 0; j < G[i].size(); j++) { lt[G[i][j]] = j; rt[G[i][j]] = G[i].size() - 1 - j; // cout << lt[G[i][j]] << " " << rt[G[i][j]] << endl; } } // cout<<"?2\n"; for (int i = 0, ed; i < cnt; i++) { ed = G[i].size() - 1; for (ll j = 0; j <= ed; j++) { sum[G[i][j] + 1] += ((j + 1) * (ed - j) - j * (ed - j + 1)); // cout << G[i][j] + 1 << " " << sum[G[i][j] + 1] << endl; } } // cout<<"?3\n"; for (int i = 0; i < n; i++) { sum[i + 1] += sum[i]; ans[a[i] + 1] -= sum[i]; // cout << sum[i + 1] << " " << ans[a[i] + 1] << endl; } // cout<<"?4\n"; godamn = 0; for (int i = 0; i < cnt; i++) { for (auto x : G[i]) { ll num, num2, sum, sum2; num = ask(x); num2 = x - num - lt[x]; sum = godamn - num; sum2 = (n - 1 - x) - sum - rt[x]; ans[i + 1] += num * sum + num2 * sum2; // cout << num << " " << num2 << " " << sum << " " << sum2 << " " << ans[i + 1] << endl; } for (int j = 0; j < G[i].size(); j++) ans[i + 1] += (G[i].size() - j) * j; godamn += G[i].size(); for (auto x : G[i]) add(x + 1, 1); } // cout<<"?5\n"; for (int i = 0; i < cnt; i++) ans[i + 1] += ans[i]; scanf("%lld", &q); while (q--) { ll l, h; scanf("%lld%lld", &l, &h); printf("%lld\n", ans[find(h + 1, cnt)] - ans[find(l, cnt)]); } return 0; }