oj.uz

Submission #5906

# Submission time Handle Problem Language Result Execution time Memory
5906 2014-05-22T11:00:22 Z cki86201 역사적 조사 (JOI14_historical) C++
15 / 100
 4000 ms 5812 KB 
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<map>
#include<set>
using namespace std;

typedef long long ll;

int n, k, qu;
ll ans[100010];
int p[100010];
map <int,int> M;
set <ll> S;

struct qua{
	qua(){}
	qua(int s,int d):s(s),d(d){}
	int s, d, c;
	bool operator<(const qua &l)const{
		return d/k != l.d/k ? d/k < l.d/k : s < l.s;
	}
}q[100010];

int main()
{
	scanf("%d%d",&n,&qu);
	k = int(sqrt(n));
	int i;
	for(i=1;i<=n;i++)scanf("%d",p+i);
	for(i=0;i<qu;i++)scanf("%d%d",&q[i].s,&q[i].d), q[i].c = i;
	/*
	sort(q, q+qu);
	int L = 1, R = 0;
	for(i=0;i<qu;i++){
        while(L>q[i].s)S.insert(++M[p[--L]] * (ll)p[L]);
        while(R<q[i].d)S.insert(++M[p[++R]] * (ll)p[R]);
        while(L<q[i].s)S.erase(M[p[L]]-- * (ll)p[L++]);
        while(R>q[i].d)S.erase(M[p[R]]-- * (ll)p[R--]);
		ans[q[i].c] = *(--S.end());
	}
	*/
	for(i=0;i<qu;i++){
		ll a = 0;
		M.clear();
		for(int j=q[i].s;j<=q[i].d;j++)M[p[j]]++;
		map <int,int>::iterator it;
		for(it = M.begin();it!=M.end();++it)a = max(a, (ll)it->first * it->second);
		printf("%lld\n",a);
	}
//	for(i=0;i<qu;i++)printf("%lld\n",ans[i]);
	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3568 KB Output is correct
2 Correct 0 ms 3568 KB Output is correct
3 Correct 20 ms 3568 KB Output is correct
4 Correct 68 ms 3568 KB Output is correct
5 Correct 268 ms 3568 KB Output is correct
6 Correct 524 ms 3568 KB Output is correct
7 Correct 636 ms 3568 KB Output is correct
8 Correct 364 ms 3568 KB Output is correct
9 Correct 376 ms 3568 KB Output is correct
10 Correct 1268 ms 3568 KB Output is correct
11 Correct 1224 ms 3568 KB Output is correct
12 Correct 1136 ms 3568 KB Output is correct
13 Correct 1124 ms 3568 KB Output is correct
14 Correct 976 ms 3568 KB Output is correct
15 Correct 1072 ms 3568 KB Output is correct
16 Correct 404 ms 3568 KB Output is correct
17 Correct 112 ms 3568 KB Output is correct
18 Correct 1024 ms 3568 KB Output is correct
19 Correct 1272 ms 3568 KB Output is correct
20 Correct 1376 ms 3568 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3568 KB Output is correct
2 Correct 0 ms 3568 KB Output is correct
3 Correct 0 ms 3568 KB Output is correct
4 Correct 0 ms 3568 KB Output is correct
5 Correct 4 ms 3568 KB Output is correct
6 Correct 0 ms 3568 KB Output is correct
7 Correct 4 ms 3568 KB Output is correct
8 Correct 4 ms 3568 KB Output is correct
9 Correct 24 ms 3568 KB Output is correct
10 Correct 4 ms 3568 KB Output is correct
11 Correct 336 ms 3568 KB Output is correct
12 Correct 56 ms 3568 KB Output is correct
13 Correct 1688 ms 3568 KB Output is correct
14 Correct 1588 ms 3568 KB Output is correct
15 Correct 60 ms 3568 KB Output is correct
16 Execution timed out 4000 ms 5812 KB Program timed out
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1708 ms 3568 KB Output is correct
2 Execution timed out 4000 ms 3568 KB Program timed out
3 Halted 0 ms 0 KB -