Submission #871578

#	Time	Username	Problem	Language	Result	Execution time	Memory
871578		qthang2k11	Two Dishes (JOI19_dishes)	C++17	100 / 100	4130 ms	281608 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) {
		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) {
		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) {
		return get(x, 1, 1, M);
	}
} seg;
 
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];
	}
	
	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;
		}
		
		ll sum = 0;
		for (auto &elem: tmp) {
			elem.first++;
			sum += elem.second;
		}
				
		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;
			
			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;
		}
	}
	
	cout << seg.get(M) + siu;
	
	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