답안 #16663 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
16663	2015-09-03T23:16:45 Z	Qwaz	역사적 조사 (JOI14_historical)	C++14	100 / 100	353 ms	4212 KB

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.0 / 5.0

#	결과	메모리	Grader output
1	Correct	4212 KB	Output is correct
2	Correct	4212 KB	Output is correct
3	Correct	4212 KB	Output is correct
4	Correct	4212 KB	Output is correct
5	Correct	4212 KB	Output is correct
6	Correct	4212 KB	Output is correct
7	Correct	4212 KB	Output is correct
8	Correct	4212 KB	Output is correct
9	Correct	4212 KB	Output is correct
10	Correct	4212 KB	Output is correct
11	Correct	4212 KB	Output is correct
12	Correct	4212 KB	Output is correct
13	Correct	4212 KB	Output is correct
14	Correct	4212 KB	Output is correct
15	Correct	4212 KB	Output is correct

Subtask #2
10.0 / 10.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	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

Subtask #3
25.0 / 25.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	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

Subtask #4
60.0 / 60.0

#	결과	실행 시간	메모리	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

답안 #16663

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 25.0 / 25.0

Subtask #4 60.0 / 60.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
25.0 / 25.0

Subtask #4
60.0 / 60.0