kmjp's blog

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

Google Code Jam 2019 Round 1B : C. Fair Fight

GCJなんで問題文がこんなに長いの…?
https://codingcompetitions.withgoogle.com/codejam/round/0000000000051706/0000000000122838

問題

N要素の整数列C,Dと非負整数Kが与えられる。
区間[L,R]のうち、max(C[L..R])とmax(D[L..R])の差の絶対値がK以下となるものは何通りか。

解法

こういう数え上げは、片方を降順に見ていきながら、その要素を必ず含む区間において、左右をどこまで伸ばせるか見ていくとよいことが多い。
今回はCを降順に処理していこう。
C[X]およびC[Y]はすでに処理済みで、区間[X+1,Y-1]においてC[Z]が最大値とする。
この時、左端Lと右端Rをどこまで伸ばせるか考える。

手順としては、max(D[L..R])<=C[cur]+Kなものを数え上げた後、max(D[L..R])

int N;
int K;
pair<int,int> P[101010];
int D[101010];

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);};
	
	void init(){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]);
	}
};
SegTree_1<int,1<<19> st;

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	st.init();
	
	cin>>N>>K;
	
	set<int> invalid;
	invalid.insert(0);
	invalid.insert(N+1);
	ll ret=0;
	
	FOR(i,N) {
		P[i].second=i+1;
		cin>>P[i].first;
	}
	FOR(i,N) {
		cin>>x;
		st.update(i+1,x);
	}
	
	sort(P,P+N);
	reverse(P,P+N);
	FOR(i,N) {
		int cur=P[i].second;
		auto it=invalid.lower_bound(cur);
		int R=*it-1;
		it--;
		int L=*it+1;
		invalid.insert(cur);
		
		ll maL=cur+1,maR=cur-1;
		ll miL=cur+1,miR=cur-1;
		for(j=19;j>=0;j--) {
			if(maL-(1<<j)>=L && st.getval(maL-(1<<j),cur+1)<=P[i].first+K) maL-=1<<j;
			if(maR+(1<<j)<=R && st.getval(cur,maR+(1<<j)+1)<=P[i].first+K) maR+=1<<j;
			if(miL-(1<<j)>=L && st.getval(miL-(1<<j),cur+1)<P[i].first-K) miL-=1<<j;
			if(miR+(1<<j)<=R && st.getval(cur,miR+(1<<j)+1)<P[i].first-K) miR+=1<<j;
		}
		
		ret+=(cur+1-maL)*(maR+1-cur)-(cur+1-miL)*(miR+1-cur);
		
	}
	
	_P("Case #%d: %lld\n",_loop,ret);
}

まとめ

なんかCodeforcesっぽい問題。