Submission #18567

#	Time	Username	Problem	Language	Result	Execution time	Memory
18567		choyi0521	역사적 조사 (JOI14_historical)	C++14	40 / 100	4000 ms	203648 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],c[MAX_N],w[MAX_N],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)c[x]*++w[x],x });
}
int main() {
	scanf("%d %d", &n, &q);
	rtn = sqrt(n);
	for (int i = 1; i <=n; i++) scanf("%d", &a[i]),mp[a[i]]=0;
	int cnt = 0;
	for (map<int, int>::iterator it = mp.begin(); it != mp.end(); it++)
		it->second = cnt,c[cnt++]=it->first;
	for (int i = 1; i <= n; i++) a[i] = mp[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) w[a[e--]]--;
		while (s > query[i].x) add(a[--s]);
		while (s < query[i].x) w[a[s++]]--;
		while (pq.top().first != (ll)c[pq.top().second]*w[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: 25 / 25
• Subtask 4: 0 / 60