結果

問題 No.1079 まお
ユーザー QCFium
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 a
void 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0