Codeforces #542 Div1 A. Toy Train

ダメダメだった回。
https://codeforces.com/contest/1129/problem/A2

問題

円周上に並んだポイントを、電車が一方通行でぐるぐる回る。
各ポイントにはいくつかの飴が置いてあり、それぞれ送り先のポイント番号が書かれている。
各ポイントでは、飴を１個だけ積むことができ、その飴は電車が送り先ポイントを通過する際に下ろされる。
なお、異なるポイントで積んだ飴は複数載せることができる。

最適な順で飴を積むとき、電車が各ポイントを始点に回り始める場合に全部配り終えるまでの移動量を求めよ。

解法

Range Maximum Queryを解けるSegTreeを使う。
各ポイントで飴をn個積む場合、少なくともn-1周はしなければならない。
また、各ポイントで最後に積む飴は一番最寄にするのがよい。

これをもとに、各ポイントについて最後の飴を配り終える位置を設定してSegTreeで最大値を求めればよい。
円周上を動くので、2*N分の大きさのSegTreeを作っておいた方が実装がきれいになる。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=0;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=comp(v,val[entry]);
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

int N,M;
vector<int> E[5005];
SegTree_1<ll,1<<20> st,st1;

int tar[5005];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	int ma=0;
	FOR(i,M) {
		cin>>x>>y;
		x--;
		y--;
		if(y<x) y+=N;
		E[x].push_back(y);
		ma=max(ma,(int)E[x].size());
	}
	
	FOR(i,N) {
		sort(ALL(E[i]));
		reverse(ALL(E[i]));
		FOR(j,E[i].size()) {
			st.update(i,N*j+E[i][j]);
			st.update(N+i,N*j+E[i][j]+N);
		}
	}
	FOR(i,N) {
		cout<<(st.getval(i,i+N)-i)<<" ";
	}
	cout<<endl;
	
	
}

まとめ

全体で１個しか詰めないと勘違いして大幅にタイムロスした。