結果

問題 No.1031 いたずら好きなお姉ちゃん
ユーザー QCFiumQCFium
提出日時 2020-04-17 23:06:23
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 159 ms / 3,500 ms
コード長 3,456 bytes
コンパイル時間 2,238 ms
コンパイル使用メモリ 197,916 KB
実行使用メモリ 13,492 KB
最終ジャッジ日時 2024-10-03 15:01:51
合計ジャッジ時間 9,684 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

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

struct SegTree {
	int n;
	std::vector<int> data;
	SegTree (int n_) {
		for (n = 1; n < n_; n <<= 1);
		data.resize(n << 1);
	}
	void add(int i, int val) {
		for (i += n; i; i >>= 1) data[i] += val;
	}
	int sum(int l, int r) {
		int res = 0;
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if (r & 1) res += data[--r];
			if (l & 1) res += data[l++];
		}
		return res;
	}
};

int main() {
	int n = ri();
	int a[n];
	for (auto &i : a) i = ri() - 1;
	
	struct Info {
		int l_min;
		int l_max;
		int r_min;
		int r_max;
		bool is_valid() {
			return l_max > l_min && r_max > r_min;
		}
	};
	Info lower[n];
	Info upper[n];
	{
		std::pair<int, int> all[n];
		for (int i = 0; i < n; i++) all[i] = {a[i], i};
		std::set<int> set;
		std::sort(all, all + n);
		for (auto i : all) {
			auto itr = set.lower_bound(i.second);
			lower[i.second].l_max = i.second + 1;
			lower[i.second].r_min = i.second;
			lower[i.second].l_min = itr == set.begin() ? 0 : *std::prev(itr) + 1;
			lower[i.second].r_max = itr == set.end() ? n : *itr;
			set.insert(i.second);
		}
		std::reverse(all, all + n);
		set.clear();
		for (auto i : all) {
			auto itr = set.lower_bound(i.second);
			upper[i.second].l_max = i.second + 1;
			upper[i.second].r_min = i.second;
			upper[i.second].l_min = itr == set.begin() ? 0 : *std::prev(itr) + 1;
			upper[i.second].r_max = itr == set.end() ? n : *itr;
			set.insert(i.second);
		}
	}
	
	int64_t res = 0;
	{
		int r0 = 0;
		int r1 = 0;
		for (auto i : lower) if (i.is_valid()) r0++;
		for (auto i : upper) if (i.is_valid()) r1++;
		res = (int64_t) r0 * r1;
	}
	{
		SegTree tree0(n + 1);
		SegTree tree1(n + 1);
		std::sort(upper, upper + n, [] (auto i, auto j) { return i.l_max < j.l_max; });
		std::sort(lower, lower + n, [] (auto i, auto j) { return i.l_min < j.l_min; });
		int head = 0;
		for (auto i : lower) {
			while (head < n && upper[head].l_max <= i.l_min) {
				if (upper[head].is_valid()) {
					tree0.add(upper[head].r_min, 1);
					tree1.add(upper[head].r_max, 1);
				}
				head++;
			}
			if (!i.is_valid()) continue;
			res -= tree0.sum(0, tree0.n);
			res += tree0.sum(i.r_max, tree0.n);
			res += tree1.sum(0, i.r_min + 1);
		}
	}
	{
		SegTree tree0(n + 1);
		SegTree tree1(n + 1);
		std::sort(upper, upper + n, [] (auto i, auto j) { return i.l_min > j.l_min; });
		std::sort(lower, lower + n, [] (auto i, auto j) { return i.l_max > j.l_max; });
		int head = 0;
		for (auto i : lower) {
			while (head < n && upper[head].l_min >= i.l_max) {
				if (upper[head].is_valid()) {
					tree0.add(upper[head].r_min, 1);
					tree1.add(upper[head].r_max, 1);
				}
				head++;
			}
			if (!i.is_valid()) continue;
			res -= tree0.sum(0, tree0.n);
			res += tree0.sum(i.r_max, tree0.n);
			res += tree1.sum(0, i.r_min + 1);
		}
	}{
		std::sort(upper, upper + n, [] (auto i, auto j) { return i.r_min > j.r_min; });
		std::sort(lower, lower + n, [] (auto i, auto j) { return i.r_max > j.r_max; });
		int head = 0;
		for (auto i : lower) {
			while (head < n && upper[head].r_min >= i.r_max) head++;
			res -= head;
		}
		std::sort(upper, upper + n, [] (auto i, auto j) { return i.r_max < j.r_max; });
		std::sort(lower, lower + n, [] (auto i, auto j) { return i.r_min < j.r_min; });
		head = 0;
		for (auto i : lower) {
			while (head < n && upper[head].r_max <= i.r_min) head++;
			res -= head;
		}
	}
	printf("%" PRId64 "\n", res - n);
	
	return 0;
}
0