Submission #16663

#	Time	Username	Problem	Language	Result	Execution time	Memory
16663		Qwaz	역사적 조사 (JOI14_historical)	C++14	100 / 100	353 ms	4212 KiB

historic

#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long ll;
const int MAX = 100020, GROUP_SIZE = 350;

struct query {
	int s, e, index;

	int getStartGroup() const {
		return s/GROUP_SIZE+1;
	}

	bool operator < (const query &t) const {
		int g1 = getStartGroup(), g2 = t.getStartGroup();

		if (g1 == g2)
			return e < t.e;
		return g1 < g2;
	}
};

int numEvent, numQuery, qFull, impact[MAX], xList[MAX], xFull;
query queries[MAX];

ll ans[MAX];
int cnt[MAX];

void input() {
	scanf("%d%d", &numEvent, &numQuery);

	for (int i = 0; i < numEvent; i++) {
		scanf("%d", &impact[i]);
		xList[xFull++] = impact[i];
	}
	sort(xList, xList+xFull);
	xFull = unique(xList, xList+xFull)-xList;

	// renumbering
	for (int i = 0; i < numEvent; i++) {
		impact[i] = lower_bound(xList, xList+xFull, impact[i]) - xList;
	}

	for (int i = 0; i < numQuery; i++) {
		int f, s;
		scanf("%d%d", &f, &s);
		// Convert to 0-base
		queries[qFull].s = f-1;
		queries[qFull].e = s-1;
		queries[qFull].index = i;
		if (queries[qFull].e < queries[qFull].getStartGroup() * GROUP_SIZE) {
			// Calculate immediately
			ll tAns = 0;
			query &now = queries[qFull];

			for (int i = now.s; i <= now.e; i++) {
				int tImpact = impact[i];
				cnt[tImpact]++;
				tAns = max(tAns, (ll)cnt[tImpact] * xList[tImpact]);
			}

			for (int i = now.s; i <= now.e; i++) {
				int tImpact = impact[i];
				cnt[tImpact]--;
			}

			ans[i] = tAns;
		} else
			// Put into a queue
			qFull++;
	}
	sort(queries, queries+qFull);
}

void solve() {
	int currentQuery = 0;
	while (currentQuery < qFull) {
		// Init count
		for (int i = 0; i < xFull; i++)
			cnt[i] = 0;
		ll maxInRange = 0;

		int startGroup = queries[currentQuery].getStartGroup(), startIndex = startGroup * GROUP_SIZE;
		for (int lastEvent = startIndex; lastEvent < numEvent; lastEvent++) {
			int tImpact = impact[lastEvent];
			cnt[tImpact]++;
			maxInRange = max(maxInRange, (ll)cnt[tImpact] * xList[tImpact]);

			if (startGroup < queries[currentQuery].getStartGroup()) break;
			else {
				while (startGroup == queries[currentQuery].getStartGroup()
					&& currentQuery < qFull && lastEvent == queries[currentQuery].e) {
					ll tAns = maxInRange;
					query &now = queries[currentQuery];

					for (int i = now.s; i < startIndex; i++) {
						tImpact = impact[i];
						cnt[tImpact]++;
						tAns = max(tAns, (ll)cnt[tImpact] * xList[tImpact]);
					}

					for (int i = now.s; i < startIndex; i++) {
						tImpact = impact[i];
						cnt[tImpact]--;
					}

					ans[now.index] = tAns;
					currentQuery++;
				}
			}
		}
	}
}

void print() {
	for (int i = 0; i < numQuery; i++)
		printf("%lld\n", ans[i]);
}

int main() {
	input();

	solve();
	print();

	return 0;
}

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