#466134 (C++14) No.1031 いたずら好きなお姉ちゃん

提出ソース

結果

問題	No.1031 いたずら好きなお姉ちゃん
ユーザー	QCFium
提出日時	2020-04-17 23:06:23
言語	C++14 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	210 ms / 3,500 ms
コード長	3,456 bytes
コンパイル時間	2,636 ms
コンパイル使用メモリ	193,692 KB
実行使用メモリ	13,748 KB
最終ジャッジ日時	2024-04-14 15:24:22
合計ジャッジ時間	11,535 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	1 ms 6,940 KB
testcase_03	AC	7 ms 6,940 KB
testcase_04	AC	7 ms 6,940 KB
testcase_05	AC	7 ms 6,944 KB
testcase_06	AC	7 ms 6,940 KB
testcase_07	AC	7 ms 6,944 KB
testcase_08	AC	7 ms 6,944 KB
testcase_09	AC	7 ms 6,940 KB
testcase_10	AC	7 ms 6,940 KB
testcase_11	AC	158 ms 11,812 KB
testcase_12	AC	157 ms 12,004 KB
testcase_13	AC	202 ms 13,748 KB
testcase_14	AC	169 ms 12,976 KB
testcase_15	AC	190 ms 12,800 KB
testcase_16	AC	156 ms 11,132 KB
testcase_17	AC	184 ms 12,088 KB
testcase_18	AC	179 ms 12,924 KB
testcase_19	AC	190 ms 11,812 KB
testcase_20	AC	204 ms 13,272 KB
testcase_21	AC	183 ms 12,564 KB
testcase_22	AC	160 ms 12,668 KB
testcase_23	AC	159 ms 10,912 KB
testcase_24	AC	191 ms 12,968 KB
testcase_25	AC	196 ms 13,144 KB
testcase_26	AC	184 ms 12,932 KB
testcase_27	AC	168 ms 12,032 KB
testcase_28	AC	200 ms 13,156 KB
testcase_29	AC	202 ms 13,312 KB
testcase_30	AC	208 ms 12,644 KB
testcase_31	AC	210 ms 12,356 KB
testcase_32	AC	202 ms 12,220 KB
testcase_33	AC	204 ms 13,312 KB
testcase_34	AC	133 ms 12,768 KB
testcase_35	AC	128 ms 12,764 KB
testcase_36	AC	132 ms 12,640 KB
testcase_37	AC	136 ms 12,764 KB
testcase_38	AC	128 ms 12,652 KB
testcase_39	AC	116 ms 12,440 KB
testcase_40	AC	130 ms 12,488 KB
testcase_41	AC	121 ms 12,620 KB
testcase_42	AC	128 ms 12,544 KB
testcase_43	AC	126 ms 12,672 KB
testcase_44	AC	125 ms 12,484 KB
testcase_45	AC	118 ms 12,240 KB
testcase_46	AC	129 ms 12,124 KB
testcase_47	AC	133 ms 11,996 KB
testcase_48	AC	128 ms 12,148 KB
testcase_49	AC	141 ms 12,192 KB
testcase_50	AC	130 ms 12,160 KB
testcase_51	AC	154 ms 12,288 KB
testcase_52	AC	152 ms 12,132 KB
testcase_53	AC	150 ms 12,128 KB
testcase_54	AC	2 ms 6,944 KB
testcase_55	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード