답안 #6853 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
6853	2014-07-08T08:20:25 Z	gs12117	역사적 조사 (JOI14_historical)	C++	100 / 100	516 ms	5780 KB

historic

#include<stdio.h>
#include<algorithm>
#define BSIZ 300
int n,q;
int x[100100];
struct sn{
	int loc,val;
	bool operator<(const sn&r)const{
		return val<r.val;
	}
};
sn st[100100];
int a[100100];
int cpr[100100];
int qry[100100][2];
long long int ans[100100];
long long int sv[100100];
int cprn;
long long int mans;
int mocc[100100];
int c[310];
int cn;
int main(){
	int i,j,k,p,bf,df;
	scanf("%d%d",&n,&q);
	for(i=0;i<n;i++){
		scanf("%d",&x[i]);
		st[i].val=x[i];
		st[i].loc=i;
	}
	std::sort(st,st+n);
	for(i=0;i<n;i++){
		a[st[i].loc]=cprn;
		if(i==n-1||st[i].val!=st[i+1].val){
			cpr[cprn]=st[i].val;
			cprn++;
		}
	}
	for(i=0;i<q;i++){
		scanf("%d%d",&qry[i][0],&qry[i][1]);
		qry[i][0]--;
		qry[i][1]--;
		st[i].loc=i;
		st[i].val=qry[i][1];
	}
	std::sort(st,st+q);
	for(i=0;i<=(n-1)/BSIZ;i++){
		cn=0;
		for(j=0;j<BSIZ&&j+i*BSIZ<n;j++){
			if(mocc[a[j+i*BSIZ]]==1)continue;
			mocc[a[j+i*BSIZ]]=1;
			c[cn]=a[j+i*BSIZ];
			cn++;
		}
		mans=0;
		bf=i*BSIZ;
		df=i*BSIZ;
		for(j=0;j<q;j++){
			p=st[j].loc;
			if(qry[p][0]/BSIZ==i){
				for(k=bf;k<=qry[p][1];k++){
					sv[a[k]]+=cpr[a[k]];
					if(mocc[a[k]]==0&&mans<sv[a[k]])mans=sv[a[k]];
				}
				bf=qry[p][1]+1;
				if(df<qry[p][0]){
					for(k=df;k<qry[p][0];k++){
						sv[a[k]]-=cpr[a[k]];
					}
				}
				else{
					for(k=qry[p][0];k<df;k++){
						sv[a[k]]+=cpr[a[k]];
					}
				}
				df=qry[p][0];
				ans[p]=mans;
				for(k=0;k<cn;k++){
					if(sv[c[k]]>ans[p])ans[p]=sv[c[k]];
				}
			}
		}
		for(k=0;k<cprn;k++){
			if(sv[k]==0)continue;
			sv[k]=0;
		}
		for(j=0;j<cn;j++){
			mocc[c[j]]=0;
		}
	}
	for(i=0;i<q;i++){
		printf("%lld\n",ans[i]);
	}
}

Subtask #1
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	5780 KB	Output is correct
2	Correct	5780 KB	Output is correct
3	Correct	5780 KB	Output is correct
4	Correct	5780 KB	Output is correct
5	Correct	5780 KB	Output is correct
6	Correct	5780 KB	Output is correct
7	Correct	5780 KB	Output is correct
8	Correct	5780 KB	Output is correct
9	Correct	5780 KB	Output is correct
10	Correct	5780 KB	Output is correct
11	Correct	5780 KB	Output is correct
12	Correct	5780 KB	Output is correct
13	Correct	5780 KB	Output is correct
14	Correct	5780 KB	Output is correct
15	Correct	5780 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	5780 KB	Output is correct
2	Correct	0 ms	5780 KB	Output is correct
3	Correct	0 ms	5780 KB	Output is correct
4	Correct	0 ms	5780 KB	Output is correct
5	Correct	4 ms	5780 KB	Output is correct
6	Correct	4 ms	5780 KB	Output is correct
7	Correct	4 ms	5780 KB	Output is correct
8	Correct	0 ms	5780 KB	Output is correct
9	Correct	4 ms	5780 KB	Output is correct
10	Correct	4 ms	5780 KB	Output is correct
11	Correct	4 ms	5780 KB	Output is correct
12	Correct	4 ms	5780 KB	Output is correct
13	Correct	0 ms	5780 KB	Output is correct
14	Correct	4 ms	5780 KB	Output is correct
15	Correct	4 ms	5780 KB	Output is correct
16	Correct	4 ms	5780 KB	Output is correct
17	Correct	4 ms	5780 KB	Output is correct
18	Correct	4 ms	5780 KB	Output is correct
19	Correct	4 ms	5780 KB	Output is correct
20	Correct	0 ms	5780 KB	Output is correct

Subtask #3
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	5780 KB	Output is correct
2	Correct	0 ms	5780 KB	Output is correct
3	Correct	0 ms	5780 KB	Output is correct
4	Correct	0 ms	5780 KB	Output is correct
5	Correct	0 ms	5780 KB	Output is correct
6	Correct	0 ms	5780 KB	Output is correct
7	Correct	0 ms	5780 KB	Output is correct
8	Correct	4 ms	5780 KB	Output is correct
9	Correct	0 ms	5780 KB	Output is correct
10	Correct	8 ms	5780 KB	Output is correct
11	Correct	184 ms	5780 KB	Output is correct
12	Correct	12 ms	5780 KB	Output is correct
13	Correct	68 ms	5780 KB	Output is correct
14	Correct	160 ms	5780 KB	Output is correct
15	Correct	288 ms	5780 KB	Output is correct
16	Correct	284 ms	5780 KB	Output is correct
17	Correct	76 ms	5780 KB	Output is correct
18	Correct	132 ms	5780 KB	Output is correct
19	Correct	184 ms	5780 KB	Output is correct
20	Correct	92 ms	5780 KB	Output is correct

Subtask #4
60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	5780 KB	Output is correct
2	Correct	28 ms	5780 KB	Output is correct
3	Correct	60 ms	5780 KB	Output is correct
4	Correct	100 ms	5780 KB	Output is correct
5	Correct	140 ms	5780 KB	Output is correct
6	Correct	164 ms	5780 KB	Output is correct
7	Correct	220 ms	5780 KB	Output is correct
8	Correct	196 ms	5780 KB	Output is correct
9	Correct	232 ms	5780 KB	Output is correct
10	Correct	308 ms	5780 KB	Output is correct
11	Correct	292 ms	5780 KB	Output is correct
12	Correct	368 ms	5780 KB	Output is correct
13	Correct	384 ms	5780 KB	Output is correct
14	Correct	460 ms	5780 KB	Output is correct
15	Correct	516 ms	5780 KB	Output is correct
16	Correct	496 ms	5780 KB	Output is correct
17	Correct	484 ms	5780 KB	Output is correct
18	Correct	480 ms	5780 KB	Output is correct
19	Correct	480 ms	5780 KB	Output is correct
20	Correct	464 ms	5780 KB	Output is correct
21	Correct	464 ms	5780 KB	Output is correct
22	Correct	448 ms	5780 KB	Output is correct
23	Correct	448 ms	5780 KB	Output is correct
24	Correct	460 ms	5780 KB	Output is correct
25	Correct	320 ms	5780 KB	Output is correct

답안 #6853

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 25.0 / 25.0

Subtask #4 60.0 / 60.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
25.0 / 25.0

Subtask #4
60.0 / 60.0