Submission #871577

#	Time	Username	Problem	Language	Result	Execution time	Memory
871577		qthang2k11	Two Dishes (JOI19_dishes)	C++17	100 / 100	5463 ms	312736 KiB

dishes

// [+]
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
const int N = 1e6 + 5;
 
int n, m, a[N], b[N], p[N], q[N];
ll s[N], t[N];
 
ll sum_a[N], sum_b[N];
 
vector<pair<int, ll>> node[N];
 
int M;
 
const ll INF = 1e18;
 
struct Node {
	ll mx, pls, val;
	Node() {
		mx = val = -INF;
		pls = 0;
	}
};
 
struct LazySegmentTree {
	Node IT[N << 2];
	
	inline void apply_add(int id, ll w) {
		IT[id].mx += w;
		IT[id].val += w;
		IT[id].pls += w;
 	}
	
	inline void apply_max(int id, ll w) {
		IT[id].mx = max(IT[id].mx, w);
		IT[id].val = max(IT[id].val, w);
	}
	
	void push(int id) {
		if (ll &lz = IT[id].pls) {
			apply_add(id << 1, lz);
			apply_add(id << 1 | 1, lz);
			lz = 0;
		}
		ll &lz = IT[id].mx;
		if (lz != -INF) {
			apply_max(id << 1, lz);
			apply_max(id << 1 | 1, lz);
			lz = -INF;
		}
	}
	
	void update_add(int x, int y, ll w, int id, int l, int r) {
		if (l > y || r < x) return;
		if (x <= l && r <= y) 
			return apply_add(id, w);
		push(id);
		int mid = (l + r) / 2;
		update_add(x, y, w, id << 1, l, mid);
		update_add(x, y, w, id << 1 | 1, mid + 1, r);
	}
	
	inline void update_add(int x, int y, ll w) {
		// cerr << "update_add(" << x << ", " << y << ", " << w << ")\n";
		update_add(x, y, w, 1, 1, M);
	}
	
	void update_max(int x, int y, ll w, int id, int l, int r) {
		if (l > y || r < x) return;
		if (x <= l && r <= y) 
			return apply_max(id, w);
		push(id);
		int mid = (l + r) / 2;
		update_max(x, y, w, id << 1, l, mid);
		update_max(x, y, w, id << 1 | 1, mid + 1, r);
	}
	
	inline void update_max(int x, int y, ll w) {
		// cerr << "update_max(" << x << ", " << y << ", " << w << ")\n";
		update_max(x, y, w, 1, 1, M);
	}
	
	ll get(int x, int id, int l, int r) {
		if (l == r) return IT[id].val;
		push(id);
		int mid = (l + r) / 2;
		if (x <= mid) return get(x, id << 1, l, mid);
		else return get(x, id << 1 | 1, mid + 1, r);
	}
	
	inline ll get(int x) {
		// cerr << "get(" << x << ") = " << get(x, 1, 1, M) << '\n';
		return get(x, 1, 1, M);
	}
} seg;
 
ll debug[1000][1000];
 
int32_t main() {
	// cin.tie(0)->sync_with_stdio(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];
	
	for (int i = 1; i <= n; i++)
		sum_a[i] = sum_a[i - 1] + a[i];
	for (int i = 1; i <= m; i++)
		sum_b[i] = sum_b[i - 1] + b[i];
		
	for (int i = 1; i <= n; i++) {
		if (sum_a[i] > s[i]) continue;
		
		int pos = ([&] () -> int {
			int l = 1, r = m, ans = 0;
			while (l <= r) {
				int mid = (l + r) / 2;
				if (sum_a[i] + sum_b[mid] <= s[i]) {
					ans = mid;
					l = mid + 1;
				} else r = mid - 1;
			}
			return ans;
		}());
		
		node[i].emplace_back(pos, p[i]);
	}
	
	ll siu = 0;
	for (int i = 1; i <= m; i++) {
		if (sum_b[i] > t[i]) continue;
		
		int pos = ([&] () -> int {
			int l = 1, r = n, ans = 0;
			while (l <= r) {
				int mid = (l + r) / 2;
				if (sum_b[i] + sum_a[mid] <= t[i]) {
					ans = mid;
					l = mid + 1;
				} else r = mid - 1;
			}
			return ans;
		}());
		
		if (pos != n) node[pos + 1].emplace_back(i - 1, -q[i]);
		siu += q[i];
		
		// cerr << "hihi " << i << ' ' << pos << '\n';
	}
	
	// cerr << "siu " << siu << '\n';
	
	M = m + 1;
	
	seg.update_max(1, M, 0);
	
	for (int i = 1; i <= n; i++) {
		auto &cur = node[i];
		sort(cur.begin(), cur.end());
		cur.emplace_back(m, 0);
		vector<pair<int, ll>> tmp;
		
		for (const auto &elem: cur) {
			if (tmp.empty() || tmp.back().first != elem.first)
				tmp.emplace_back(elem);
			else tmp.back().second += elem.second;
		}
		
		// for (auto [j, val]: tmp)
			// debug[i][j] = val,
			// cerr << string(10, ' ') << "[" << i << ", " << j << "] = " << val << '\n';
		
		ll sum = 0;
		for (auto &elem: tmp) {
			elem.first++;
			sum += elem.second;
		}
		
		// cerr << "i = " << i << ", sum = " << sum << '\n';
		
		ll pre_max = -INF;
		for (int i = 0; i < (int)tmp.size(); i++) {
			int L = 1, R = tmp[i].first;
			if (i - 1 >= 0) L = tmp[i - 1].first + 1;
			// cerr << L << ' ' << R << '\n';
			
			seg.update_add(L, R, sum);
			if (L - 1 > 0) pre_max = max(pre_max, seg.get(L - 1));
			seg.update_max(L, R, pre_max);
			
			sum -= tmp[i].second;
		}
		
		// ll pre_max = LLONG_MIN;
		// for (const auto &elem: tmp) {
			// int pos = upper_bound(arr.begin(), arr.end(), elem.first) - arr.begin();
// 			
			// dp[pos] = max(dp[pos] + sum, pre_max);
// 			
			// pre_max = max(pre_max, dp[pos]);
			// sum -= elem.second;
		// }
		
		// cerr << "at i = " << i << '\n';
		// for (const auto &elem: tmp)
			// cerr << elem.first << ' ' << elem.second << '\n';
// 		
		// for (int j = 1; j <= M; j++)
			// fprintf(stderr, "dp[%d][%d] = %lld\n", i, j - 1, seg.get(j));
		// cerr << '\n';
	}
	
	// cerr << "siu = " << siu << '\n';
	
	cout << seg.get(M) + siu;
	
	// for (int i = m; i >= 0; i--)
		// for (int j = 1; j <= n; j++)
			// cerr << debug[j][i] << "\t\n"[j == n];
	
	return 0;
}

• 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