結果
問題 | No.1079 まお |
ユーザー |
![]() |
提出日時 | 2020-07-04 15:07:10 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 732 ms / 2,000 ms |
コード長 | 1,765 bytes |
コンパイル時間 | 1,698 ms |
コンパイル使用メモリ | 187,224 KB |
実行使用メモリ | 13,440 KB |
最終ジャッジ日時 | 2024-09-19 02:27:27 |
合計ジャッジ時間 | 14,082 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>int ri() {int n;scanf("%d", &n);return n;}std::vector<int> a;int k;int64_t res = 0;// use from avoid merge(const std::vector<int> &a, const std::vector<int> &b) {int n = a.size();int m = b.size();int min = 1000000001;int cnt = 0;struct Info {int min;int cnt;int64_t sum;bool operator < (const Info &rhs) const {return min < rhs.min;}};std::map<int, std::vector<Info> > single;for (int i = 0; i < n; i++) {if (min > a[i]) min = a[i], cnt = 1;else if (min == a[i]) cnt++;if (cnt > 1) continue;single[a[i]].push_back({min, 1, i});}for (auto &i : single) {std::sort(i.second.begin(), i.second.end());std::vector<Info> tmp;for (auto j : i.second) {if (!tmp.size() || tmp.back().min != j.min) tmp.push_back(j);else tmp.back().cnt += j.cnt, tmp.back().sum += j.sum;}for (int j = 0; j + 1 < (int) tmp.size(); j++) {tmp[j + 1].cnt += tmp[j].cnt;tmp[j + 1].sum += tmp[j].sum;}i.second = tmp;}min = 1000000001;for (int i = 0; i < m; i++) {min = std::min(min, b[i]);auto &r0 = single[k - b[i]];auto itr = std::lower_bound(r0.begin(), r0.end(), Info{min, 0, 0});if (itr != r0.begin()) {itr--;res += itr->sum;res += (int64_t) itr->cnt * (i + 2);}}}void solve(int l, int r) {if (r - l == 1) {if (a[l] * 2 == k) res += 1;return;}int m = l + ((r - l) >> 1);std::vector<int> r0(a.begin() + l, a.begin() + m);std::reverse(r0.begin(), r0.end());std::vector<int> r1(a.begin() + m, a.begin() + r);merge(r0, r1);merge(r1, r0);solve(l, m);solve(m, r);}int main() {int n = ri();k = ri();a.resize(n);for (auto &i : a) i = ri();solve(0, n);printf("%" PRId64 "\n", res);return 0;}