#506870 (C++14) No.1079 まお

• 問題: No.1079 まお
• ユーザー: QCFium
• 提出日時: 2020-07-04 14:18:08
• 言語: C++14 (gcc 13.2.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 1,247 bytes
• コンパイル時間: 1,852 ms
• コンパイル使用メモリ: 185,284 KB
• 実行使用メモリ: 28,828 KB
• 最終ジャッジ日時: 2023-10-19 04:17:04
• 合計ジャッジ時間: 14,453 ms
• ジャッジサーバーID （参考情報）: judge11 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,348 KB
testcase_01	AC	2 ms; 4,348 KB
testcase_02	AC	2 ms; 4,348 KB
testcase_03	AC	2 ms; 4,348 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	AC	327 ms; 16,208 KB
testcase_13	AC	388 ms; 18,712 KB
testcase_14	AC	509 ms; 21,104 KB
testcase_15	AC	572 ms; 23,588 KB
testcase_16	AC	643 ms; 26,084 KB
testcase_17	WA	-
testcase_18	AC	695 ms; 25,304 KB
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	AC	777 ms; 28,828 KB
testcase_23	AC	779 ms; 28,824 KB
testcase_24	AC	797 ms; 28,824 KB
testcase_25	AC	817 ms; 28,824 KB
testcase_26	AC	825 ms; 28,824 KB
testcase_27	AC	25 ms; 4,348 KB
testcase_28	AC	321 ms; 17,892 KB
testcase_29	AC	467 ms; 25,700 KB
testcase_30	AC	463 ms; 25,700 KB
testcase_31	AC	37 ms; 4,348 KB

ソースコード

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

std::vector<int> a;
int k;

int64_t res = 0;
void solve(int l, int r) {
	if (r - l == 1) {
		if (a[l] * 2 == k) res += 1;
		return;
	}
	int m = l + ((r - l) >> 1);
	int min = 1000000001;
	int cnt = 0;
	std::map<int, std::pair<int, int64_t> > right; // val : {cnt, index sum}
	std::map<std::pair<int, int>, std::pair<int, int64_t> > right_special; // {val, min} : {cnt, index sum}
	for (int i = m; i < r; i++) {
		if (min > a[i]) min = a[i], cnt = 1;
		else if (min == a[i]) cnt++;
		if (cnt > 1) continue;
		auto &r0 = right[a[i]];
		r0.first++;
		r0.second += i;
		auto &r1 = right_special[{a[i], min}];
		r1.first++;
		r1.second += i;
	}
	min = 1000000001;
	cnt = 0;
	for (int i = m - 1; i >= l; i--) {
		if (min > a[i]) min = a[i], cnt = 1;
		else if (min == a[i]) cnt++;
		if (cnt > 1) continue;
		auto &r0 = right[k - a[i]];
		auto &r1 = right_special[{k - a[i], min}];
		int cnt = r0.first - r1.first;
		int64_t sum = r0.second - r1.second;
		res += sum;
		res -= (int64_t) cnt * (i - 1);
	}
	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;
}