记录编号	253479	评测结果	AAAAAAAAAA
题目名称	求和	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.381 s
提交时间	2016-04-22 10:48:22	内存使用	2.66 MiB

#include<cstdio>
#include<cstdlib>
const int maxn=100005;
int a[maxn],b[maxn];
struct node{
	int key,lch,rch,prt,ord;
	node(int _k=0,int _p=0){
		key=_k;
		prt=_p;
		lch=rch=0;
		ord=rand();
	}
};
struct treap{
	node t[maxn];
	int _size,root;
	treap(){
		_size=1;
		root=0;
	}
	void lrot(int rt){
		int p=t[rt].prt,r=t[rt].rch;
		if(rt==root){
			root=r;
		}else{
			if(rt==t[p].lch)t[p].lch=r;
			else t[p].rch=r;
		}
		t[r].prt=p;
		t[rt].rch=t[r].lch;
		if(t[r].lch)t[t[r].lch].prt=rt;
		t[r].lch=rt;
		t[rt].prt=r;
	}
	void rrot(int rt){
		int p=t[rt].prt,l=t[rt].lch;
		if(rt==root){
			root=l;
		}else{
			if(rt==t[p].lch)t[p].lch=l;
			else t[p].rch=l;
		}
		t[l].prt=p;
		t[rt].lch=t[l].rch;
		if(t[l].rch)t[t[l].rch].prt=rt;
		t[l].rch=rt;
		t[rt].prt=l;
	}
	void insert(int x,int rt){
		if(root==0){
			root=1;
			t[_size++]=node(x);
			return;
		}
		if(x==t[rt].key)return;
		if(x<t[rt].key){
			if(t[rt].lch)insert(x,t[rt].lch);
			else{
				t[rt].lch=_size;
				t[_size++]=node(x,rt);
			}
			if(t[t[rt].lch].ord>t[rt].ord)rrot(rt);
		}else{
			if(t[rt].rch)insert(x,t[rt].rch);
			else{
				t[rt].rch=_size;
				t[_size++]=node(x,rt);
			}
			if(t[t[rt].rch].ord>t[rt].ord)lrot(rt);
		}
	}
	void insert(int x){
		insert(x,root);
	}
	int getmin(){
		int rt=root;
		while(t[rt].lch)rt=t[rt].lch;
		return t[rt].key;
	}
	int succ(int x,int rt){
		if(rt==0)return -1;
		if(t[rt].key<=x)return succ(x,t[rt].rch);
		int tmp=succ(x,t[rt].lch);
		return (tmp>0)?tmp:t[rt].key;
	}
	int succ(int x){
		return succ(x,root);
	}
	int pred(int x,int rt){
		if(rt==0)return -1;
		if(t[rt].key>=x)return pred(x,t[rt].lch);
		int tmp=pred(x,t[rt].rch);
		return tmp>0?tmp:t[rt].key;
	}
	int pred(int x){
		return pred(x,root);
	}
}tree;
int main(){
	freopen("suma.in","r",stdin);
	freopen("suma.out","w",stdout);
	int n,k,p,ans=10000000;
	scanf("%d %d %d",&n,&k,&p);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
		b[i]=(b[i-1]+a[i])%p;
	}
	tree.insert(0);
	int tmp1,tmp2,now;
	for(int i=1;i<=n;++i){
		//process
		if(b[i]>=k){
			tmp1=tree.pred(b[i]-k+1);
			if(tmp1>0&&b[i]-tmp1<ans)ans=b[i]-tmp1;
		}
		tmp2=tree.pred(b[i]+p-k);
		if(tmp2>0&&b[i]+p-tmp2<ans)ans=b[i]+p-tmp2;
		tree.insert(b[i]);
	}
	printf("%d",ans);
	fclose(stdin);fclose(stdout);
	return 0;
}