记录编号	292364	评测结果	AAAAAAAAAA
题目名称	求和	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.603 s
提交时间	2016-08-08 20:00:56	内存使用	0.30 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100010;
struct node{//Splay Tree
	int data,size;
	node *lch,*rch,*prt;
	node(int d=0):data(d),size(1),lch(NULL),rch(NULL),prt(NULL){}
	void refresh(){
		size=1;
		if(lch)size+=lch->size;
		if(rch)size+=rch->size;
	}
}*root=NULL;
int mod(int,int);
void insert(node*,node* =root);
node *previous(int,node* =root);
void splay(node*,node* =NULL);
void lrot(node*);
void rrot(node*);
int n,k,p,sum=0,x,ans=0x7fffffff;
node *y;
int main(){
#define MINE
#ifdef MINE
	freopen("suma.in","r",stdin);
	freopen("suma.out","w",stdout);
#endif
	scanf("%d%d%d",&n,&k,&p);
	insert(new node(0));
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		sum=(sum+x)%p;
		y=previous(mod(sum-k,p));
		if(y)ans=min(ans,mod(sum-y->data,p));
		insert(new node(sum));
	}
	printf("%d",ans);
	return 0;
}
inline int mod(int x,int p){
	while(x<0)x+=p;
	return x%p;
}
void insert(node *x,node *rt){
	if(!root){
		root=x;
		return;
	}
	for(;;){
		if(x->data<rt->data){
			if(rt->lch)rt=rt->lch;
			else{
				rt->lch=x;
				break;
			}
		}
		else{
			if(rt->rch)rt=rt->rch;
			else{
				rt->rch=x;
				break;
			}
		}
	}
	x->prt=rt;
	splay(rt);
}
node *previous(int x,node *rt){
	node *y=NULL;
	while(rt){
		if(rt->data<=x){
			if(!y||rt->data>y->data)y=rt;
			rt=rt->rch;
		}
		else rt=rt->lch;
	}
	return y;
}
void splay(node *x,node *tar){
	for(node *rt=x->prt;rt!=tar;rt=x->prt){
		if(rt->prt==tar){
			if(x==rt->lch)rrot(rt);
			else lrot(rt);
			break;
		}
		if(rt==rt->prt->lch){
			if(x==rt->lch){
				rrot(rt->prt);
				rrot(rt);
			}
			else{
				lrot(rt);
				rrot(x->prt);
			}
		}
		else{
			if(x==rt->rch){
				lrot(rt->prt);
				lrot(rt);
			}
			else{
				rrot(rt);
				lrot(x->prt);
			}
		}
	}
}
void lrot(node *x){
	if(!x)return;
	node *y=x->rch;
	if(!y)return;
	y->prt=x->prt;
	if(x->prt){
		if(x==x->prt->lch)x->prt->lch=y;
		else x->prt->rch=y;
	}
	else root=y;
	x->rch=y->lch;
	if(y->lch)y->lch->prt=x;
	x->prt=y;
	y->lch=x;
	x->refresh();
	y->refresh();
}
void rrot(node *x){
	if(!x)return;
	node *y=x->lch;
	if(!y)return;
	y->prt=x->prt;
	if(x->prt){
		if(x==x->prt->lch)x->prt->lch=y;
		else x->prt->rch=y;
	}
	else root=y;
	x->lch=y->rch;
	if(y->rch)y->rch->prt=x;
	x->prt=y;
	y->rch=x;
	x->refresh();
	y->refresh();
}