记录编号	142476	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]信号塔	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.315 s
提交时间	2014-12-09 15:03:41	内存使用	3.20 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define MX 4000000
const int SIZEN=100010;
class Point{
public:
	int x,y;
	void assign(int x_,int y_){
		x=x_,y=y_;
	}
};
void print(Point p){printf("(%d %d)",p.x,p.y);}
Point turn(Point a){
	return (Point){a.x+a.y,a.x-a.y};
}
void printreal(Point p){
	int a=p.x,b=p.y;
	//x+y=a,x-y=b
	printf("%d %d\n",(a+b)/2,(a-b)/2);
}
class Rect{
public:
	int x1,y1,x2,y2;//1是较小者,2是较大者
	void zoom(int dlt){
		x1-=dlt;y1-=dlt;
		x2+=dlt;y2+=dlt;
	}
	void assign(Point p1,Point p2){
		x1=p1.x,y1=p1.y,x2=p2.x,y2=p2.y;
	}
	void assign(int x1_,int y1_,int x2_,int y2_){
		x1=x1_,y1=y1_,x2=x2_,y2=y2_;
	}
	void operator = (Point p){
		assign(p,p);
	}
};
void print(Rect A){
	printf("(%d %d)->(%d %d)\n",A.x1,A.y1,A.x2,A.y2);
}
Rect intersection(Rect A,Rect B){
	A.x1=max(A.x1,B.x1),A.y1=max(A.y1,B.y1);
	A.x2=min(A.x2,B.x2),A.y2=min(A.y2,B.y2);
	return A;
}
Point decide(Rect A){
	Point p;p.assign(A.x1,A.y1);
	if((p.x+p.y)&1) p.x++;
	return p;
}
int N,M;
int D[SIZEN]={0};
vector<Point> client[SIZEN];
Rect scope[SIZEN];
void work(void){
	for(int i=0;i<=N;i++) scope[i].assign(-MX,-MX,MX,MX);//0其实没用
	for(int i=N;i>=1;i--){
		for(int j=0;j<client[i].size();j++){
			Rect now;now=client[i][j];
			now.zoom(D[i]);
			scope[i]=intersection(scope[i],now);
		}
		Rect now=scope[i];//i=1时不要在意
		now.zoom(D[i]);now.zoom(-D[i-1]);
		scope[i-1]=intersection(scope[i-1],now);
	}
	Rect now;now.assign(-MX,-MX,MX,MX);
	for(int i=1;i<=N;i++){
		now=intersection(now,scope[i]);
		Point p=decide(now);
		printreal(p);
		now=p;
		if(i<N) now.zoom(D[i+1]-D[i]);
	}
}
void read(void){
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++) scanf("%d",&D[i]);
	Point p;int u;
	for(int i=1;i<=M;i++){
		scanf("%d%d%d",&u,&p.x,&p.y);
		client[u].push_back(turn(p));
	}
}
int main(){
	freopen("lanwuni.in","r",stdin);
	freopen("lanwuni.out","w",stdout);
	read();
	work();
	return 0;
}