Codeforces #625 Div1 C. World of Darkraft : Battle for Azathoth

典型っぽいんだけど本番しょうもないミスで落とした。
https://codeforces.com/contest/1320/problem/C

問題

N種類の武器とM種類の防具があり、それぞれの攻撃力・守備力と購入時の金額が与えられる。
また、P種類の敵がおり、それぞれの攻撃力・守備力・獲得金額が与えられる。

武器と防具を1つずつ買い、敵を倒すことを考える。
その際、敵の防御力を上回る攻撃力を持つ武器と、敵の攻撃力を上回る防御力を持つ防具を持っているなら、獲得金額が得られるとする。
(獲得金額の総和)-(武器・防具の購入金額)の最大値を求めよ。

解法

区間加算・区間最大値を求めるSegTreeを使う。
まず、各防御力を達成するのに必要な最低金額の分、SegTree上で0から減算しておく。
攻撃力の低い順に武器を走査しよう。
それより防御力の低い敵は、防具次第で倒せることになるので、SegTreeでその敵を倒せる防御力に対し獲得金額を加算する。
あとはこの状態でSegTreeの最大値を求めれば、今見ている武器に対し、(獲得できる金額)-(防具の購入金額)の最大値を取得できる。

int N,M,P;
pair<int,int> A[202020];
ll BC[1<<20];
int X[202020],Y[202020],Z[202020];

static ll const def=-1LL<<60;
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	SegTree_3(){
		int i;
		val.resize(NV*2,0); ma.resize(NV*2,0);
	};
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return ma[k];
		return val[k]+max(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	
	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]+=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]=val[k]+max(ma[k*2],ma[k*2+1]);
		}
	}
};
SegTree_3<ll,1<<20> st;
vector<pair<int,int>> ev[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d%d",&N,&M,&P);
	
	FOR(i,N) scanf("%d%d",&A[i].first,&A[i].second);
	FOR(i,1<<20) BC[i]=-1LL<<60;
	FOR(i,M) {
		scanf("%d%d",&x,&y);
		BC[x]=max(BC[x],(ll)-y);
	}
	
	for(i=(1<<20)-2;i>=0;i--) BC[i]=max(BC[i],BC[i+1]);
	FOR(i,1<<20) st.update(i,i+1,BC[i]);
	
	FOR(i,P) {
		scanf("%d%d%d",&X[i],&Y[i],&Z[i]);
		ev[X[i]].push_back({Y[i],Z[i]});
	}
	
	ll ma=-1LL<<60;
	sort(A,A+N);
	int pre=0;
	FOR(i,N) {
		while(pre<A[i].first) {
			FORR(e,ev[pre]) {
				st.update(e.first+1,1<<20,e.second);
			}
			pre++;
		}
		ll sc=-A[i].second+st.getval(0,1<<20);
		ma=max(ma,sc);
	}
	cout<<ma<<endl;
	
	
}

まとめ

これ落としたのもったいないな。