Submission #18566

#	Time	Username	Problem	Language	Result	Execution time	Memory
18566		choyi0521	역사적 조사 (JOI14_historical)	C++14	15 / 100	4000 ms	202456 KiB

historic

#include<stdio.h>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAX_N=1e5,MAX_Q = 1e5;
int n, q,a[MAX_N+1],rtn;
ll res[MAX_Q];
priority_queue<pair<ll, int>> pq;
map<int, int> mp;
struct st {
	int x, y, idx;
	bool operator<(st i) const{
		return x / rtn*rtn + y / rtn<i.x/rtn*rtn+i.y/rtn;
	}
}query[MAX_Q];
void add(int x) {
	pq.push({ (ll)x*++mp[x],x });
}
int main() {
	scanf("%d %d", &n, &q);
	rtn = sqrt(n);
	for (int i = 1; i <=n; i++) scanf("%d", &a[i]);
	for (int i = 0; i < q; i++) {
		scanf("%d %d", &query[i].x, &query[i].y);
		query[i].idx = i;
	}
	sort(query, query + q);
	int s=0, e = -1;
	for (int i = 0; i < q; i++) {
		while (e < query[i].y) add(a[++e]);
		while (e > query[i].y) mp[a[e--]]--;
		while (s > query[i].x) add(a[--s]);
		while (s < query[i].x) mp[a[s++]]--;
		while (pq.top().first != (ll)pq.top().second*mp[pq.top().second]) pq.pop();
		res[query[i].idx] = pq.top().first;
	}
	for (int i = 0; i < q; i++)printf("%lld\n", res[i]);
	return 0;
}

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