TIOJ 1566 簡單易懂的現代都市

poao899    34672K    4151MS    G++     1.71K     2009-09-24 12:22:20                              .

這題寫過一段時間了

不過因為這題太可愛了還是放上來好了XD







deque超神秘

當初聽SKYLY學長講到說是deque O(n)時超驚悚的XD



不過寫得怪醜醜的QQ

而且超邪惡的

這題測資有tab !!

害我gn炸了好幾次QQ


/***********************************************

#include<stdio.h>
#define MAX 10002000
unsigned n,m,k;
unsigned i,l,r,cnt;
unsigned in[10000000];
bool getint(unsigned *a){
	unsigned g=0;char c=getchar();
	if(c==EOF)return 0;
	while(c==10||c==32||c==9)c=getchar();
	while(c>='0'&&c<='9'){
		g=g*10+c-'0';
		c=getchar();
	}
	*a=g;
	return 0;
}
unsigned out[10000000][2];
struct queue{
	unsigned q[MAX];
	unsigned front,rear;
	void ini(){
		front=0;
		rear=1;
	}
	unsigned popf(){
		unsigned c=q[front];
		front=++front%MAX;
		return c;
	}
	unsigned popr(){
		rear=(--rear+MAX)%MAX;
		return q[rear];
	}
	unsigned peekf(){
		return q[front];
	}
	unsigned peekr(){
		unsigned x=(rear-1+MAX)%MAX;
		return q[x];
	}
	void pushf(unsigned c){
		front=(--front+MAX)%MAX;
		q[front]=c;
	}
	void pushr(unsigned c){
		q[rear]=c;
		rear=++rear%MAX;
	}
}max,min;

void mover(unsigned &r){
	if(++r < n){
		bool b=0;
		while(max.front!=max.rear){
			if(max.peekf()>=in[r])
				break;
			max.popf();
		}
		max.pushf(in[r]);
		while(min.front!=min.rear){
			if(min.peekf()<=in[r])
				break;
			min.popf();
		}
		min.pushf(in[r]);
	}
}
void movel(unsigned &l){
	if(l+1 < n){
		if(min.peekr()==in[l])
			min.popr();
		if(max.peekr()==in[l])
			max.popr();
		l++;
	}
}
main(){
	getint(&n);getint(&m);getint(&k);
	//scanf("%u%u%u",&n,&m,&k);
	for(i=0;i<n;i++)
		getint(in+i);
		//scanf("%u",&in[i]);
	max.ini();
	min.ini();
	max.q[0]=in[0];
	min.q[0]=in[0];
	for(l=r=0;l<n-1||r<n-1;){
		if(max.peekr()-min.peekr() == k){
			out[cnt][0]=l;
			out[cnt][1]=r;
			cnt++;
		}
		if(l || r-l+1==m)
			movel(l);
		if(r!=n-1)
			mover(r);		
	}
	printf("%d\n",cnt);
	for(i=0;i<cnt;i++)
		printf("%d %d\n",out[i][0]+1,out[i][1]+1);
}