#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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
4368 KB |
Output is correct |
2 |
Correct |
0 ms |
4368 KB |
Output is correct |
3 |
Correct |
0 ms |
4368 KB |
Output is correct |
4 |
Correct |
0 ms |
4368 KB |
Output is correct |
5 |
Correct |
0 ms |
4368 KB |
Output is correct |
6 |
Correct |
0 ms |
4368 KB |
Output is correct |
7 |
Correct |
0 ms |
4368 KB |
Output is correct |
8 |
Correct |
0 ms |
4368 KB |
Output is correct |
9 |
Correct |
0 ms |
4368 KB |
Output is correct |
10 |
Correct |
0 ms |
4368 KB |
Output is correct |
11 |
Correct |
0 ms |
4368 KB |
Output is correct |
12 |
Correct |
0 ms |
4368 KB |
Output is correct |
13 |
Correct |
0 ms |
4368 KB |
Output is correct |
14 |
Correct |
0 ms |
4368 KB |
Output is correct |
15 |
Correct |
0 ms |
4368 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4368 KB |
Output is correct |
2 |
Correct |
1 ms |
4500 KB |
Output is correct |
3 |
Correct |
3 ms |
4504 KB |
Output is correct |
4 |
Correct |
10 ms |
4760 KB |
Output is correct |
5 |
Correct |
26 ms |
5152 KB |
Output is correct |
6 |
Correct |
53 ms |
5148 KB |
Output is correct |
7 |
Correct |
48 ms |
5920 KB |
Output is correct |
8 |
Correct |
51 ms |
4756 KB |
Output is correct |
9 |
Correct |
50 ms |
5144 KB |
Output is correct |
10 |
Correct |
44 ms |
7524 KB |
Output is correct |
11 |
Correct |
49 ms |
7516 KB |
Output is correct |
12 |
Correct |
47 ms |
7508 KB |
Output is correct |
13 |
Correct |
43 ms |
7500 KB |
Output is correct |
14 |
Correct |
48 ms |
7480 KB |
Output is correct |
15 |
Correct |
52 ms |
7492 KB |
Output is correct |
16 |
Correct |
51 ms |
4756 KB |
Output is correct |
17 |
Correct |
45 ms |
4500 KB |
Output is correct |
18 |
Correct |
46 ms |
7488 KB |
Output is correct |
19 |
Correct |
52 ms |
7528 KB |
Output is correct |
20 |
Correct |
38 ms |
10620 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
4368 KB |
Output is correct |
2 |
Correct |
0 ms |
4368 KB |
Output is correct |
3 |
Correct |
0 ms |
4368 KB |
Output is correct |
4 |
Correct |
0 ms |
4368 KB |
Output is correct |
5 |
Correct |
0 ms |
4524 KB |
Output is correct |
6 |
Correct |
0 ms |
4368 KB |
Output is correct |
7 |
Correct |
2 ms |
4552 KB |
Output is correct |
8 |
Correct |
5 ms |
4900 KB |
Output is correct |
9 |
Correct |
13 ms |
5460 KB |
Output is correct |
10 |
Correct |
19 ms |
4368 KB |
Output is correct |
11 |
Correct |
1334 ms |
53524 KB |
Output is correct |
12 |
Correct |
33 ms |
5928 KB |
Output is correct |
13 |
Correct |
496 ms |
53832 KB |
Output is correct |
14 |
Correct |
1243 ms |
55400 KB |
Output is correct |
15 |
Correct |
1547 ms |
203648 KB |
Output is correct |
16 |
Correct |
180 ms |
21348 KB |
Output is correct |
17 |
Correct |
59 ms |
16664 KB |
Output is correct |
18 |
Correct |
102 ms |
28952 KB |
Output is correct |
19 |
Correct |
148 ms |
21348 KB |
Output is correct |
20 |
Correct |
90 ms |
15204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
144 ms |
5144 KB |
Output is correct |
2 |
Correct |
478 ms |
10552 KB |
Output is correct |
3 |
Correct |
818 ms |
53752 KB |
Output is correct |
4 |
Correct |
1474 ms |
103244 KB |
Output is correct |
5 |
Correct |
1773 ms |
103408 KB |
Output is correct |
6 |
Correct |
2577 ms |
53764 KB |
Output is correct |
7 |
Correct |
3385 ms |
16688 KB |
Output is correct |
8 |
Correct |
3636 ms |
10520 KB |
Output is correct |
9 |
Correct |
3914 ms |
7444 KB |
Output is correct |
10 |
Execution timed out |
4000 ms |
7444 KB |
Program timed out |
11 |
Halted |
0 ms |
0 KB |
- |