oj.uz

Submission #18566

# Submission time Handle Problem Language Result Execution time Memory
18566 2016-02-09T08:59:38 Z choyi0521 역사적 조사 (JOI14_historical) C++14
15 / 100
 4000 ms 202456 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3584 KB Output is correct
2 Correct 0 ms 3584 KB Output is correct
3 Correct 0 ms 3584 KB Output is correct
4 Correct 1 ms 3584 KB Output is correct
5 Correct 0 ms 3584 KB Output is correct
6 Correct 0 ms 3584 KB Output is correct
7 Correct 0 ms 3584 KB Output is correct
8 Correct 0 ms 3584 KB Output is correct
9 Correct 0 ms 3584 KB Output is correct
10 Correct 0 ms 3584 KB Output is correct
11 Correct 0 ms 3584 KB Output is correct
12 Correct 0 ms 3584 KB Output is correct
13 Correct 0 ms 3584 KB Output is correct
14 Correct 0 ms 3584 KB Output is correct
15 Correct 0 ms 3584 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3584 KB Output is correct
2 Correct 0 ms 3584 KB Output is correct
3 Correct 5 ms 3716 KB Output is correct
4 Correct 15 ms 3972 KB Output is correct
5 Correct 44 ms 4368 KB Output is correct
6 Correct 86 ms 4364 KB Output is correct
7 Correct 84 ms 5136 KB Output is correct
8 Correct 75 ms 3972 KB Output is correct
9 Correct 77 ms 4356 KB Output is correct
10 Correct 98 ms 6740 KB Output is correct
11 Correct 102 ms 6732 KB Output is correct
12 Correct 95 ms 6724 KB Output is correct
13 Correct 94 ms 6716 KB Output is correct
14 Correct 94 ms 6696 KB Output is correct
15 Correct 103 ms 6708 KB Output is correct
16 Correct 76 ms 3972 KB Output is correct
17 Correct 51 ms 3716 KB Output is correct
18 Correct 93 ms 6704 KB Output is correct
19 Correct 107 ms 6744 KB Output is correct
20 Correct 95 ms 9836 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3584 KB Output is correct
2 Correct 0 ms 3584 KB Output is correct
3 Correct 0 ms 3584 KB Output is correct
4 Correct 0 ms 3584 KB Output is correct
5 Correct 5 ms 3716 KB Output is correct
6 Correct 2 ms 3584 KB Output is correct
7 Correct 0 ms 3720 KB Output is correct
8 Correct 6 ms 4004 KB Output is correct
9 Correct 18 ms 4536 KB Output is correct
10 Correct 19 ms 3584 KB Output is correct
11 Correct 1597 ms 52740 KB Output is correct
12 Correct 42 ms 5140 KB Output is correct
13 Correct 843 ms 53032 KB Output is correct
14 Correct 2579 ms 53684 KB Output is correct
15 Execution timed out 4000 ms 202456 KB Program timed out
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 4356 KB Output is correct
2 Correct 875 ms 9760 KB Output is correct
3 Correct 1938 ms 52896 KB Output is correct
4 Correct 3769 ms 102448 KB Output is correct
5 Execution timed out 4000 ms 102592 KB Program timed out
6 Halted 0 ms 0 KB -