Submission #13626

#	Time	Username	Problem	Language	Result	Execution time	Memory
13626		gs12117	Mountain Trek Route (IZhO12_route)	C++98	100 / 100	227 ms	21536 KiB

route

#include<stdio.h>
#include<queue>
int n;
int a[1001000];
int b[1001000];
int m;
int ans;
int liv[1001000];
int nxt[1001000];
int prv[1001000];
struct node{
	int stp;
	int len;
	bool operator<(const node&r)const{
		return len>r.len;
	}
};
std::priority_queue<node> pq;
int main(){
	int i,j;
	node p;
	scanf("%d%d",&n,&m);
	j=0;
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
		if(a[i]>a[j])j=i;
	}
	for(i=0;i<n;i++){
		b[i]=a[(i+j)%n];
	}
	b[n]=b[0];
	n++;
	j=-1;
	for(i=0;i<n;i++){
		if(i==0||b[i]!=b[i-1]){
			liv[i]=1;
			prv[i]=j;
			j=i;
		}
	}
	j=n;
	for(i=n-1;i>=0;i--){
		if(liv[i]==1){
			nxt[i]=j;
			j=i;
			if(nxt[i]!=n&&prv[i]!=-1&&b[nxt[i]]>b[i]&&b[prv[i]]>b[i]){
				p.len=nxt[i]-i;
				p.stp=i;
				pq.push(p);
			}
		}
	}
	while(m>0&&pq.size()!=0){
		p=pq.top();
		pq.pop();
		i=p.stp;
		j=m/p.len;
		if(j<b[nxt[i]]-b[i]&&j<b[prv[i]]-b[i]){
			ans+=j;
			break;
		}
		else{
			if(b[nxt[i]]-b[i]>b[prv[i]]-b[i]){
				j=b[prv[i]]-b[i];
			}
			else{
				j=b[nxt[i]]-b[i];
			}
			ans+=j;
			b[i]+=j;
			m-=j*p.len;
			if(b[i]==b[prv[i]]){
				i=prv[i];
				nxt[i]=nxt[nxt[i]];
				prv[nxt[i]]=i;
			}
			if(b[i]==b[nxt[i]]){
				nxt[i]=nxt[nxt[i]];
				prv[nxt[i]]=i;
			}
			if(nxt[i]!=n&&prv[i]!=-1&&b[nxt[i]]>b[i]&&b[prv[i]]>b[i]){
				p.len=nxt[i]-i;
				p.stp=i;
				pq.push(p);
			}
		}
	}
	printf("%d",ans*2);
}

• Subtask 1: 100 / 100