Submission #501388

#	Time	Username	Problem	Language	Result	Execution time	Memory
501388		zhougz	역사적 조사 (JOI14_historical)	C++17	100 / 100	1039 ms	7772 KiB

historic

/**
 *    author: zhougz
 *    created: 03/01/2022 10:55:06
**/
#include "bits/stdc++.h"

using namespace std;

int blk_sz;

struct query {
	int l, r, idx;
	bool operator<(const query &rhs) const {
		return l / blk_sz != rhs.l / blk_sz ? l < rhs.l : (r < rhs.r) ^ ((l / blk_sz) & 1);
	}
};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	blk_sz = n / sqrt(q);
	vector<int> arr(n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	vector<query> queries(q);
	for (int i = 0; i < q; i++) {
		cin >> queries[i].l >> queries[i].r;
		queries[i].l--;
		queries[i].r--;
		queries[i].idx = i;
	}
	sort(queries.begin(), queries.end());
	vector<int> v(arr.begin(), arr.end());
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	vector<int> idx(n);
	for (int i = 0; i < n; i++) {
		idx[i] = lower_bound(v.begin(), v.end(), arr[i]) - v.begin();
	}
	const int N = 1 << (int)ceil(log2(v.size()));
	vector<long long> t(2 * N);
	auto update = [&](int x, int val) {
		t[x += N] += val;
		while ((x >>= 1) != 0) {
			t[x] = max(t[x << 1], t[(x << 1) + 1]);
		}
	};
	auto add = [&](int x) {
		update(idx[x], arr[x]);
	};
	auto remove = [&](int x) {
		update(idx[x], -arr[x]);
	};
	vector<long long> res(q);
	int cur_l = 0, cur_r = -1;
	for (const auto &[l, r, idx] : queries) {
		while (cur_l < l) {
			remove(cur_l++);
		}
		while (cur_l > l) {
			add(--cur_l);
		}
		while (cur_r < r) {
			add(++cur_r);
		}
		while (cur_r > r) {
			remove(cur_r--);
		}
		res[idx] = t[1];
	}
	for (auto x : res) {
		cout << x << '\n';
	}
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 60 / 60