IOI2004 Hermes

1回の手紙を持っていくのに途中で曲がるのは無駄なので縦移動か横移動しかない、ということを考察してDPを考え、
DPをSegment Treeで高速化するテクがこんな時代からIOIに出ていたとは……
AtCoderをみると他の人300ms弱とかで通しているのですが、こんな実行時間じゃ本番環境だと絶対TLEなんじゃないでしょうか。僕は44msで通しました。

#include<stdio.h>
#include<algorithm>
using namespace std;
int x[30000];
int y[30000];
int segtree[4][4096];
void update(int a,int b,int c){
	b+=2048;
	while(b){
		segtree[a][b]=min(segtree[a][b],c);
		b/=2;
	}
}
int query(int t,int a,int b,int c,int d,int e){
	if(d<a||b<c)return 1010101010;
	if(c<=a&&b<=d)return segtree[t][e];
	return min(query(t,a,(a+b)/2,c,d,e*2),query(t,(a+b)/2+1,b,c,d,e*2+1));
}
int ABS(int a){return max(a,-a);}
int AD=1000;
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d%d",x+i+1,y+i+1);
	for(int i=0;i<4;i++)
		for(int j=0;j<4096;j++)
			segtree[i][j]=1010101010;
	update(0,AD,0);
	update(1,AD,0);
	update(2,AD,0);
	update(3,AD,0);
	int yoko=0;
	int tate=0;
	for(int i=0;i<a;i++){
		int yval=min(query(0,0,2047,0,y[i+1]+AD,1)+y[i+1],query(1,0,2047,y[i+1]+AD,2047,1)-y[i+1])+yoko;
		int tval=min(query(2,0,2047,0,x[i+1]+AD,1)+x[i+1],query(3,0,2047,x[i+1]+AD,2047,1)-x[i+1])+tate;
		yoko+=ABS(x[i+1]-x[i]);
		tate+=ABS(y[i+1]-y[i]);
		update(0,y[i]+AD,tval-yoko-y[i]);
		update(1,y[i]+AD,tval-yoko+y[i]);
		update(2,x[i]+AD,yval-tate-x[i]);
		update(3,x[i]+AD,yval-tate+x[i]);
	}
	int ret=1010101010;
	for(int i=0;i<2048;i++){
		ret=min(ret,query(0,0,2047,i,i,1)+yoko+i-AD);
		ret=min(ret,query(2,0,2047,i,i,1)+tate+i-AD);
	}
	printf("%d\n",ret);
}