Codeforces ECR #073 : F. Choose a Square

幾何と思ったらあんまり関係なかった。
https://codeforces.com/contest/1221/problem/F

問題

２次元座標上でN個の点の座標とスコアが与えられる。
ここで、対角線が直線y=xに乗るような軸に平行な正方形を１個考える。
この正方形のスコアは、内包する点のスコアの合計から1辺の長さを引いたものとする。
スコアの最大値を求めよ。

解法

区間加算と区間最大値が利用できるSegTreeを用いる。
座標圧縮したうえで、y=x上を順に走査していこう。
例えばY座標がX座標より大きな点を考えると、この点は操作位置がY座標を超えた段階で、左下点がそのX座標より小さくした場合に加算対象となるので、SegTreeへの加算と考えることができる。
長さでスコアが減少するのは、事前に(y=x直線上の走査位置の)点のスコアからX座標分足しておけばよい。

int N;
int X[505050],Y[505050],C[505050];

template<class V,int NV> class SegTree_3 {
public:
	vector<V> val;
	vector<pair<V,int>> ma;
	SegTree_3(){
		int i;
		val.resize(NV*2); ma.resize(NV*2);
		FOR(i,NV) val[i+NV]=0, ma[i+NV]={0,i};
		for(i=NV-1;i>=1;i--) ma[i]=max(ma[2*i],ma[2*i+1]);
	};
	
	pair<V,int> getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return {-1LL<<60,0};
		if(x<=l && r<=y) return ma[k];
		auto a=max(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
		a.first+=val[k];
		return a;
	}
	
	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].first+=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]=max(ma[k*2],ma[k*2+1]);
			ma[k].first+=val[k];
		}
	}
};

SegTree_3<ll,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	vector<ll> V;
	V.push_back(0);
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>Y[i]>>C[i];
		if(X[i]>Y[i]) swap(X[i],Y[i]);
		V.push_back(X[i]);
		V.push_back(Y[i]);
	}
	sort(ALL(V));
	V.erase(unique(ALL(V)),V.end());
	st.update(0,2*N+2,-1LL<<60);
	FOR(i,V.size()) {
		st.update(i,i+1,(1LL<<60)+V[i]);
	}
	
	map<int,vector<int>> ev;
	FOR(i,N) {
		X[i]=lower_bound(ALL(V),X[i])-V.begin();
		Y[i]=lower_bound(ALL(V),Y[i])-V.begin();
		ev[Y[i]].push_back(i);
	}
	ll ma=0;
	ll x1=1LL<<30,x2=1LL<<30;
	FORR(e,ev) {
		auto VV=e.second;
		FORR(c,VV) st.update(0,X[c]+1,C[c]);
		auto ret=st.getval(0,e.first+1);
		ret.first-=V[e.first];
		//cout<<V[e.first]<<" - "<<V[ret.second]<<" "<<ret.first<<endl;
		if(ret.first>ma) {
			ma=ret.first;
			x1=V[ret.second];
			x2=V[e.first];
		}
		//FORR(c,VV) st.update(0,X[c],-C[c]);
		
	}
	cout<<ma<<endl;
	cout<<x1<<" "<<x1<<" "<<x2<<" "<<x2<<endl;
}

まとめ

ちょっと状態遷移混乱したけど、こっちは普通に解けた。