oj.uz

답안 #789723

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
789723 2023-07-21T20:46:31 Z IBory 역사적 조사 (JOI14_historical) C++17
5 / 100
 30 ms 2524 KB 
#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;

const int MAX = 123456, SQ = 8;
ll X[MAX], ans[MAX], cnt[MAX], S[MAX];
priority_queue<ll> PQ[MAX >> 8], E[MAX >> 8];

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) {
	int n = S[idx];
	priority_queue<ll>& C = PQ[n >> SQ];
	priority_queue<ll>& EPQ = E[n >> SQ];
	if (cnt[n]) EPQ.push(X[n] * cnt[n]);
	C.push(X[n] * (++cnt[n]));
}

void Sub(int idx) {
	int n = S[idx];
	priority_queue<ll>& C = PQ[n >> SQ];
	priority_queue<ll>& EPQ = E[n >> SQ];
	EPQ.push(X[n] * cnt[n]);
	if (--cnt[n]) C.push(X[n] * (cnt[n]));
}

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++);
		for (int i = 0; i < (MAX >> SQ); ++i) {
			if (PQ[i].empty()) continue;
			while (!E[i].empty() && PQ[i].top() == E[i].top()) PQ[i].pop(), E[i].pop();
			ans[id] = max(ans[id], PQ[i].top());
		}
	}

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

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1748 KB Output is correct
2 Correct 1 ms 1748 KB Output is correct
3 Correct 2 ms 1748 KB Output is correct
4 Correct 2 ms 1748 KB Output is correct
5 Correct 2 ms 1748 KB Output is correct
6 Correct 5 ms 1748 KB Output is correct
7 Correct 2 ms 1808 KB Output is correct
8 Correct 2 ms 1808 KB Output is correct
9 Correct 1 ms 1808 KB Output is correct
10 Correct 1 ms 1748 KB Output is correct
11 Correct 1 ms 1808 KB Output is correct
12 Correct 2 ms 1876 KB Output is correct
13 Correct 1 ms 1808 KB Output is correct
14 Correct 1 ms 1748 KB Output is correct
15 Correct 1 ms 1748 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1748 KB Output is correct
2 Correct 1 ms 1748 KB Output is correct
3 Correct 2 ms 1748 KB Output is correct
4 Correct 2 ms 1748 KB Output is correct
5 Correct 2 ms 1748 KB Output is correct
6 Correct 5 ms 1748 KB Output is correct
7 Correct 2 ms 1808 KB Output is correct
8 Correct 2 ms 1808 KB Output is correct
9 Correct 1 ms 1808 KB Output is correct
10 Correct 1 ms 1748 KB Output is correct
11 Correct 1 ms 1808 KB Output is correct
12 Correct 2 ms 1876 KB Output is correct
13 Correct 1 ms 1808 KB Output is correct
14 Correct 1 ms 1748 KB Output is correct
15 Correct 1 ms 1748 KB Output is correct
16 Correct 2 ms 1876 KB Output is correct
17 Correct 6 ms 2132 KB Output is correct
18 Correct 12 ms 2332 KB Output is correct
19 Incorrect 30 ms 2524 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1808 KB Output is correct
2 Correct 1 ms 1748 KB Output is correct
3 Correct 1 ms 1748 KB Output is correct
4 Correct 3 ms 1812 KB Output is correct
5 Incorrect 3 ms 1876 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1748 KB Output is correct
2 Correct 1 ms 1748 KB Output is correct
3 Correct 2 ms 1748 KB Output is correct
4 Correct 2 ms 1748 KB Output is correct
5 Correct 2 ms 1748 KB Output is correct
6 Correct 5 ms 1748 KB Output is correct
7 Correct 2 ms 1808 KB Output is correct
8 Correct 2 ms 1808 KB Output is correct
9 Correct 1 ms 1808 KB Output is correct
10 Correct 1 ms 1748 KB Output is correct
11 Correct 1 ms 1808 KB Output is correct
12 Correct 2 ms 1876 KB Output is correct
13 Correct 1 ms 1808 KB Output is correct
14 Correct 1 ms 1748 KB Output is correct
15 Correct 1 ms 1748 KB Output is correct
16 Correct 2 ms 1876 KB Output is correct
17 Correct 6 ms 2132 KB Output is correct
18 Correct 12 ms 2332 KB Output is correct
19 Incorrect 30 ms 2524 KB Output isn't correct
20 Halted 0 ms 0 KB -