답안 #16663

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
16663 2015-09-03T23:16:45 Z Qwaz 역사적 조사 (JOI14_historical) C++14
100 / 100
353 ms 4212 KB
#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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 4212 KB Output is correct
2 Correct 0 ms 4212 KB Output is correct
3 Correct 0 ms 4212 KB Output is correct
4 Correct 0 ms 4212 KB Output is correct
5 Correct 0 ms 4212 KB Output is correct
6 Correct 0 ms 4212 KB Output is correct
7 Correct 0 ms 4212 KB Output is correct
8 Correct 0 ms 4212 KB Output is correct
9 Correct 0 ms 4212 KB Output is correct
10 Correct 0 ms 4212 KB Output is correct
11 Correct 0 ms 4212 KB Output is correct
12 Correct 0 ms 4212 KB Output is correct
13 Correct 0 ms 4212 KB Output is correct
14 Correct 0 ms 4212 KB Output is correct
15 Correct 0 ms 4212 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 4212 KB Output is correct
2 Correct 0 ms 4212 KB Output is correct
3 Correct 0 ms 4212 KB Output is correct
4 Correct 2 ms 4212 KB Output is correct
5 Correct 5 ms 4212 KB Output is correct
6 Correct 7 ms 4212 KB Output is correct
7 Correct 7 ms 4212 KB Output is correct
8 Correct 7 ms 4212 KB Output is correct
9 Correct 7 ms 4212 KB Output is correct
10 Correct 8 ms 4212 KB Output is correct
11 Correct 8 ms 4212 KB Output is correct
12 Correct 8 ms 4212 KB Output is correct
13 Correct 8 ms 4212 KB Output is correct
14 Correct 9 ms 4212 KB Output is correct
15 Correct 10 ms 4212 KB Output is correct
16 Correct 8 ms 4212 KB Output is correct
17 Correct 8 ms 4212 KB Output is correct
18 Correct 8 ms 4212 KB Output is correct
19 Correct 8 ms 4212 KB Output is correct
20 Correct 8 ms 4212 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 4212 KB Output is correct
2 Correct 0 ms 4212 KB Output is correct
3 Correct 0 ms 4212 KB Output is correct
4 Correct 0 ms 4212 KB Output is correct
5 Correct 0 ms 4212 KB Output is correct
6 Correct 0 ms 4212 KB Output is correct
7 Correct 3 ms 4212 KB Output is correct
8 Correct 5 ms 4212 KB Output is correct
9 Correct 11 ms 4212 KB Output is correct
10 Correct 12 ms 4212 KB Output is correct
11 Correct 83 ms 4212 KB Output is correct
12 Correct 38 ms 4212 KB Output is correct
13 Correct 66 ms 4212 KB Output is correct
14 Correct 101 ms 4212 KB Output is correct
15 Correct 80 ms 4212 KB Output is correct
16 Correct 197 ms 4212 KB Output is correct
17 Correct 105 ms 4212 KB Output is correct
18 Correct 161 ms 4212 KB Output is correct
19 Correct 160 ms 4212 KB Output is correct
20 Correct 80 ms 4212 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 4212 KB Output is correct
2 Correct 34 ms 4212 KB Output is correct
3 Correct 61 ms 4212 KB Output is correct
4 Correct 83 ms 4212 KB Output is correct
5 Correct 113 ms 4212 KB Output is correct
6 Correct 149 ms 4212 KB Output is correct
7 Correct 175 ms 4212 KB Output is correct
8 Correct 188 ms 4212 KB Output is correct
9 Correct 214 ms 4212 KB Output is correct
10 Correct 264 ms 4212 KB Output is correct
11 Correct 260 ms 4212 KB Output is correct
12 Correct 256 ms 4212 KB Output is correct
13 Correct 284 ms 4212 KB Output is correct
14 Correct 313 ms 4212 KB Output is correct
15 Correct 353 ms 4212 KB Output is correct
16 Correct 347 ms 4212 KB Output is correct
17 Correct 344 ms 4212 KB Output is correct
18 Correct 334 ms 4212 KB Output is correct
19 Correct 320 ms 4212 KB Output is correct
20 Correct 306 ms 4212 KB Output is correct
21 Correct 307 ms 4212 KB Output is correct
22 Correct 303 ms 4212 KB Output is correct
23 Correct 305 ms 4212 KB Output is correct
24 Correct 293 ms 4212 KB Output is correct
25 Correct 271 ms 4212 KB Output is correct