topcoder

kojingharangの日記

2012-04-09

VK Cup 2012 Round 3 (Unofficial Div. 2 Edition)

19:28 |

ooo-- +-0 (Rank 51) 1640->1653

Round 3 と同時開催の Div2。

日本の上位陣スゲェと思いながらsystem testを見てた。

174 C. Range Increments

19:28 |

0-10^5の数字が1-10^5個入った配列が与えられる。全部 0 の状態から始めて与えられた配列にするには、L番目の数からR番目の数を +1 する操作を最低何回すればいいか。

苦手な雰囲気がぷんぷんする
最大値が連続してるとこを削ってく方法だと、最大値 M, 個数 N として O(NM) かかるのでだめ

なんかスタックを使って O(N) でできる雰囲気がする
左から見て行って、topの値より大きかったら push, 小さかったら top が表す区間が終わるので pop すると同時に (L, R) と呼ぶ回数を記録する
スタックに入れる値としては、区間の高さと始まりの位置でよさそう
ならしコストを考えると push した分しか pop しないので O(N)
push するときの始まりの位置は、最後に pop した区間の始まりの位置と同じにするとかいうあたりが面倒
なんかぐちゃぐちゃしてて怪しい
どっかミスっててもおかしくないけど通った

int main() {
	int N;
	cin>>N;
	vector<PII> st(100010);
	vector<pair<PII, int> > ans(100010);
	int ansp=0;
	int anscount=0;
	int stp=0;
	REP(i, N) {
		int v;
		cin>>v;
		int push_pos=i;
		while(stp>0 && st[stp-1].second > v) {
			push_pos = st[stp-1].first;
			//cout<<"push_pos "<<push_pos<<endl;
			int prevH = max(v, stp-1>0 ? st[stp-2].second : 0);
			ans[ansp++] = MP(MP(st[stp-1].first+1, i), st[stp-1].second - prevH);
			anscount += st[stp-1].second - prevH;
			stp--;
		}
		if(stp==0) {
			if(v>0) st[stp++] = MP(push_pos, v);
		} else if(st[stp-1].second < v) {
			st[stp++] = MP(push_pos, v);
		}
		//REP(m, stp) cout<<st[m]<<" "; cout<<endl;
	}
	while(stp>0) {
		int prevH = stp-1>0 ? st[stp-2].second : 0;
		ans[ansp++] = MP(MP(st[stp-1].first+1, N), st[stp-1].second-prevH);
		anscount += st[stp-1].second-prevH;
		stp--;
	}
	
	cout<<anscount<<endl;
	REP(i, ansp) {
		REP(j, ans[i].second) {
			cout<<ans[i].first.first<<" "<<ans[i].first.second<<endl;
		}
	}
	
	return 0;
}