Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-05-01SRM336,SRM337,SRM338 (Practice)

SRM 337 BuildingAdvertise

|  SRM 337 BuildingAdvertise - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 337 BuildingAdvertise - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7473

  • 僕の苦手なデータ構造を利用するタイプの問題。
    • やり方がいろいろあるらしい(スタックを使ったり、分割統治法をしたり。)
    • 要復習

public class BuildingAdvertise {
	class Tower {
		int pos;
		long height;
		Tower(int p, long h) {
			pos = p;
			height = h;
		}
	}
	
	public long getMaxArea(int[] h, int n) {
		long[] r = new long[n+1];
		int j = 0;
		int m = h.length;
		for (int i = 0 ; i < n ; i++) {
			r[i] = h[j];
			int s = (j + 1) % m;
			h[j] = ((h[j] ^ h[s]) + 13) % 835454957;
			j = s;
		}
		r[n] = 0;
		n++;
		
		Tower[] towers = new Tower[n+1];
		int tidx = -1;
		long ans = 0;
		for (int i = 0 ; i < n ; i++) {
			if (tidx == -1 || towers[tidx].height < r[i]) {
				tidx++;
				towers[tidx] = new Tower(i, r[i]);
				continue;
			} else {
				if (towers[tidx].height == r[i]) {
					continue;
				}
				
				int pos = 0;
				while (tidx >= 0 && towers[tidx].height > r[i]) {
					long width = i - towers[tidx].pos;
					long S = width * towers[tidx].height;
					ans = Math.max(ans, S);
					
					pos = towers[tidx].pos;
					tidx--;
				}
				tidx++;
				towers[tidx] = new Tower(pos, r[i]);
			}
		}
		return ans;
	}
}