oj.uz

Submission #5909

# Submission time Handle Problem Language Result Execution time Memory
5909 2014-05-22T11:52:11 Z cki86201 역사적 조사 (JOI14_historical) C++
40 / 100
 4000 ms 11888 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], a;
int p[100010];
map <int,int> M;
multiset <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 : (((d/k)&1) ? s < l.s : 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){
			a = ++M[p[--L]] * (ll)p[L];
			S.insert(a);
			if(a != p[L])S.erase(S.find(a - p[L]));
		}
		while(R<q[i].d){
			a = ++M[p[++R]] * (ll)p[R];
			S.insert(a);
			if(a != p[R])S.erase(S.find(a - p[R]));
		}
		while(L<q[i].s){
			a = M[p[L]]-- * (ll)p[L];
			S.erase(S.find(a));
			if(a != p[L])S.insert(a - p[L]);
			++L;
		}
		while(R>q[i].d){
			a = M[p[R]]-- * (ll)p[R];
			S.erase(S.find(a));
			if(a != p[R])S.insert(a - p[R]);
			--R;
		}
		ans[q[i].c] = *S.rbegin();
	}
	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 3572 KB Output is correct
2 Correct 0 ms 3572 KB Output is correct
3 Correct 0 ms 3572 KB Output is correct
4 Correct 0 ms 3572 KB Output is correct
5 Correct 0 ms 3572 KB Output is correct
6 Correct 0 ms 3572 KB Output is correct
7 Correct 0 ms 3572 KB Output is correct
8 Correct 0 ms 3572 KB Output is correct
9 Correct 0 ms 3572 KB Output is correct
10 Correct 0 ms 3572 KB Output is correct
11 Correct 0 ms 3572 KB Output is correct
12 Correct 0 ms 3572 KB Output is correct
13 Correct 0 ms 3572 KB Output is correct
14 Correct 0 ms 3572 KB Output is correct
15 Correct 0 ms 3572 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3572 KB Output is correct
2 Correct 0 ms 3572 KB Output is correct
3 Correct 4 ms 3572 KB Output is correct
4 Correct 16 ms 3572 KB Output is correct
5 Correct 40 ms 3572 KB Output is correct
6 Correct 80 ms 3572 KB Output is correct
7 Correct 88 ms 3572 KB Output is correct
8 Correct 60 ms 3572 KB Output is correct
9 Correct 68 ms 3572 KB Output is correct
10 Correct 100 ms 3704 KB Output is correct
11 Correct 100 ms 3704 KB Output is correct
12 Correct 96 ms 3572 KB Output is correct
13 Correct 100 ms 3572 KB Output is correct
14 Correct 100 ms 3572 KB Output is correct
15 Correct 100 ms 3572 KB Output is correct
16 Correct 68 ms 3572 KB Output is correct
17 Correct 28 ms 3572 KB Output is correct
18 Correct 100 ms 3572 KB Output is correct
19 Correct 96 ms 3704 KB Output is correct
20 Correct 100 ms 3704 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3572 KB Output is correct
2 Correct 0 ms 3572 KB Output is correct
3 Correct 0 ms 3572 KB Output is correct
4 Correct 0 ms 3572 KB Output is correct
5 Correct 0 ms 3572 KB Output is correct
6 Correct 0 ms 3572 KB Output is correct
7 Correct 4 ms 3572 KB Output is correct
8 Correct 4 ms 3704 KB Output is correct
9 Correct 24 ms 3836 KB Output is correct
10 Correct 16 ms 3572 KB Output is correct
11 Correct 132 ms 3572 KB Output is correct
12 Correct 80 ms 3572 KB Output is correct
13 Correct 148 ms 3836 KB Output is correct
14 Correct 188 ms 5420 KB Output is correct
15 Correct 208 ms 6212 KB Output is correct
16 Correct 268 ms 10568 KB Output is correct
17 Correct 76 ms 3572 KB Output is correct
18 Correct 148 ms 3572 KB Output is correct
19 Correct 172 ms 9116 KB Output is correct
20 Correct 116 ms 11888 KB Output is correct

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 3572 KB Output is correct
2 Correct 816 ms 3572 KB Output is correct
3 Correct 2244 ms 3968 KB Output is correct
4 Execution timed out 4000 ms 4628 KB Program timed out
5 Halted 0 ms 0 KB -