| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 789723 |
2023-07-21T20:46:31 Z |
IBory |
역사적 조사 (JOI14_historical) |
C++17 |
|
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;
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
