kmjp's blog

競技プログラミング参加記です

yukicoder : No.631 Noelちゃんと電車旅行

自分のアカウント名を題材に?と思ったらなり切り系アカウントなのかな。
https://yukicoder.me/problems/no/631

問題

1~N番のN個の駅が並んでいる。
i番の駅からはT[i]分以降1分毎に電車が(i+1)番の駅に向かい発車する。
駅間の移動時間は固定で3分である。

以下のクエリを順次処理せよ。
駅の区間[L,R]と遅延時間Dが与えられる。T[L]~T[R]がD加算されたとき、1番の駅を時刻0に出発したとき、N番の駅の到着時刻はどうなるか。

解法

途中の駅で待つのも最初の駅で待つのも同じなので、最初の駅でまとめて待つことを考えよう。
i番の駅で待たないためには、1番の駅でT[i]-3*(i-1)だけ待ってから出発すればよい。

言い換えれば、最初の駅で全駅におけるmax(T[i]-3*(i-1))だけ待つのが最適である。
よって、区間加算および区間最大値算出が可能なSegTreeを使い、max(T[i]-3*(i-1))を順次求めていこう。

int N;
int T[101010];

static ll const def=-1LL<<40;
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	SegTree_3(){
		int i;
		val.resize(NV*2,0); ma.resize(NV*2,0);
		FOR(i,NV) val[i+NV]=ma[i+NV]=def;
		for(i=NV-1;i>=1;i--) ma[i]=max(ma[2*i],ma[2*i+1]);
	};
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return ma[k];
		return val[k]+max(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=val[k]+max(ma[k*2],ma[k*2+1]);
		}
	}
};

SegTree_3<ll,1<<20> st;
int M,L,R,X;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x;
		x-=i*3;
		st.update(i,i+1,(1LL<<40)+x);
	}
	cin>>M;
	while(M--) {
		cin>>L>>R>>X;
		st.update(L-1,R,X);
		ll ma=st.getval(0,N-1);
		cout<<(ma+(N-1)*3)<<endl;
	}
}

まとめ

新年割と良いスタートが切れて良かったです。