Submission #789717

#	Time	Username	Problem	Language	Result	Execution time	Memory
789717		IBory	역사적 조사 (JOI14_historical)	C++17	40 / 100	4043 ms	13640 KiB

historic

#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;

const int MAX = 100007, SQ = 8;
ll X[MAX], ans[MAX], cnt[MAX], S[MAX];
multiset<ll> cand;

struct Query {
	int s, e, id;
	Query(int a = 0, int b = 0, int c = 0) {
		s = a, e = b, id = c;
	}
	const bool operator<(Query& a) {
		if ((s >> SQ) != (a.s >> SQ)) return (s >> SQ) < (a.s >> SQ);
		return e > a.e;
	}
} QS[MAX];

void Add(int idx) {
	if (cnt[S[idx]]) cand.erase(cand.find(X[idx] * cnt[S[idx]]));
	cand.insert(X[idx] * (++cnt[S[idx]]));
}

void Sub(int idx) {
	cand.erase(cand.find(X[idx] * cnt[S[idx]]));
	if (--cnt[S[idx]]) cand.insert(X[idx] * cnt[S[idx]]);
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, Q;
	cin >> N >> Q;
	map<int, int> occur;
	for (int i = 1; i <= N; ++i) {
		cin >> X[i];
		if (occur.find(X[i]) == occur.end()) S[i] = occur[X[i]] = i;
		else S[i] = occur[X[i]];
	}
	for (int i = 0; i < Q; ++i) {
		int s, e;
		cin >> s >> e;
		QS[i] = Query(s, e, i);
	}
	sort(QS, QS + Q);

	int L = 1, R = 0;
	for (int i = 0; i < Q; ++i) {
		auto [s, e, id] = QS[i];
		while (R < e) Add(++R);
		while (s < L) Add(--L);
		while (e < R) Sub(R--);
		while (L < s) Sub(L++);
		ans[id] = *cand.rbegin();
	}

	for (int i = 0; i < Q; ++i) cout << ans[i] << '\n';
	return 0;
}

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