Submission #768103

#	Time	Username	Problem	Language	Result	Execution time	Memory
768103		qwerasdfzxcl	Two Dishes (JOI19_dishes)	C++17	100 / 100	3704 ms	259708 KiB

dishes

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr ll INF = 4e18;

struct Foo{
	ll a, b;
	bool id;

	Foo(){}

	ll calc(ll x){return max(a, x) + b;}

	void operator += (const Foo &F){
		if (!id) {*this = F; return;}

		a = (a+b > F.a)?a:(F.a - b);
		b += F.b;
	}
};

struct Seg{
	ll ans[1101000];
	Foo lazy[2202000];
	
	void propagate(int i, int l, int r){
		if (!lazy[i].id) return;

		if (l==r) ans[l] = lazy[i].calc(ans[l]);
		else{
			lazy[i<<1] += lazy[i];
			lazy[i<<1|1] += lazy[i]; 
		}

		lazy[i].id = 0;
	}

	void add(int i, int l, int r, int s, int e, int x){
		propagate(i, l, r);
		if (r<s || e<l) return;
		if (s<=l && r<=e){
			lazy[i].a = -INF, lazy[i].b = x, lazy[i].id = 1;
			propagate(i, l, r);
			return;
		}

		int m = (l+r)>>1;
		add(i<<1, l, m, s, e, x); add(i<<1|1, m+1, r, s, e, x);
	}

	void max(int i, int l, int r, int s, int e, ll x){
		propagate(i, l, r);
		if (r<s || e<l) return;
		if (s<=l && r<=e){
			lazy[i].a = x, lazy[i].b = 0, lazy[i].id = 1;
			propagate(i, l, r);
			return;
		}

		int m = (l+r)>>1;
		max(i<<1, l, m, s, e, x); max(i<<1|1, m+1, r, s, e, x);
	}

	ll query(int i, int l, int r, int p){
		propagate(i, l, r);
		if (l==r) return ans[l];

		int m = (l+r)>>1;
		if (p<=m) return query(i<<1, l, m, p);
		return query(i<<1|1, m+1, r, p);
	}
}tree;

int n, m;
int A[1001000], B[1001000], P[1001000], Q[1001000], mxA[1001000], mxB[1001000];
ll S[1001000], T[1001000], sumA[1001000], sumB[1001000], ans;
vector<pair<int, int>> lowerQ[1001000], upperQ[1001000];

void init(){
	for (int i=1;i<=n;i++) sumA[i] = sumA[i-1] + A[i];
	for (int i=1;i<=m;i++) sumB[i] = sumB[i-1] + B[i];
 
	for (int i=1;i<=n;i++){
		mxB[i] = upper_bound(sumB, sumB+m+1, S[i] - sumA[i]) - sumB - 1;

		if (P[i] > 0){
			if (mxB[i] >= 0) lowerQ[i-1].emplace_back(mxB[i], P[i]);
		}

		else if (P[i] < 0){
			ans += P[i];
			if (mxB[i] < m) upperQ[i-1].emplace_back(mxB[i]+1, -P[i]);
		}
		
	}
	for (int i=1;i<=m;i++){
		mxA[i] = upper_bound(sumA, sumA+n+1, T[i] - sumB[i]) - sumA - 1;

		if (Q[i] > 0){
			if (mxA[i]==n) ans += Q[i];
			else if (mxA[i] >= 0) upperQ[mxA[i]].emplace_back(i, Q[i]);
		}

		else if (Q[i] < 0){
			ans += Q[i];
			if (mxA[i]==-1) ans -= Q[i];
			else if (mxA[i] < n) lowerQ[mxA[i]].emplace_back(i-1, -Q[i]);
		}
		
	}

	for (int i=0;i<n;i++){
		sort(lowerQ[i].begin(), lowerQ[i].end(), greater<pair<int, int>>());
		sort(upperQ[i].begin(), upperQ[i].end());
	}

}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	cin >> n >> m;
	for (int i=1;i<=n;i++) cin >> A[i] >> S[i] >> P[i];
	for (int i=1;i<=m;i++) cin >> B[i] >> T[i] >> Q[i];
 
	init();
 
	for (int x=0;x<n;x++){
		for (auto &[y, val]:upperQ[x]) tree.add(1, 0, m, y, m, val);
		for (auto &[y, val]:lowerQ[x]){
			tree.add(1, 0, m, 0, y, val);
			tree.max(1, 0, m, y+1, m, tree.query(1, 0, m, y));
		}
	}
 
	printf("%lld\n", tree.query(1, 0, m, m) + ans);
}

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 17 / 17
• Subtask 8: 9 / 9