Submission #1220267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220267		siewjh	Two Dishes (JOI19_dishes)	C++20	100 / 100	5294 ms	285844 KiB

dishes

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1000005;
ll prefa[MAXN], tla[MAXN], pta[MAXN], prefb[MAXN], tlb[MAXN], ptb[MAXN];
vector<pair<int, ll>> pts[MAXN];
struct node{
	int s, e, m; ll mxv, ladd, lset; bool bset;
	node *l, *r;
	node (int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1; mxv = 0, ladd = 0, lset = 0, bset = 0;
		if (s != e){
			l = new node(s, m); r = new node(m + 1, e);
		}
	}
	void pset(ll v){
		mxv = v; ladd = 0; lset = v; bset = 1;
	}
	void padd(ll v){
		mxv += v; ladd += v;
	}
	void prop(){
		if (s == e) return;
		if (bset){
			l->pset(lset); r->pset(lset);
			bset = 0;
		}
		if (ladd != 0){
			l->padd(ladd); r->padd(ladd);
			ladd = 0;
		}
	}
	void uset(int x, int y, ll v){
		prop();
		if (x == s && y == e){
			pset(v); return;
		}
		else if (y <= m) l->uset(x, y, v);
		else if (x > m) r->uset(x, y, v);
		else{
			l->uset(x, m, v); r->uset(m + 1, y, v);
		}
		mxv = max(l->mxv, r->mxv);
	}
	void uadd(int x, int y, ll v){
		prop();
		if (x == s && y == e){
			padd(v); return;
		}
		else if (y <= m) l->uadd(x, y, v);
		else if (x > m) r->uadd(x, y, v);
		else{
			l->uadd(x, m, v); r->uadd(m + 1, y, v);
		}
		mxv = max(l->mxv, r->mxv);
	}
	ll query(int x){
		prop();
		if (s == e) return mxv;
		else if (x <= m) return l->query(x);
		else return r->query(x);
	}
	int search(int x, int y, ll v){
		prop();
		if (x == s && y == e){
			if (mxv < v) return e;
			if (s == e) return s - 1;
			return (l->mxv >= v ? l->search(x, m, v) : r->search(m + 1, y, v));
		}
		else if (y <= m) return l->search(x, y, v);
		else if (x > m) return r->search(x, y, v);
		else{
			int res = l->search(x, m, v);
			return (res != m ? res : r->search(m + 1, y, v));
		}
	}
};
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N, M; cin >> N >> M;
	for (int i = 1; i <= N; i++){
		ll a; cin >> a >> tla[i] >> pta[i];
		prefa[i] = prefa[i - 1] + a;
	}
	for (int i = 1; i <= M; i++){
		ll b; cin >> b >> tlb[i] >> ptb[i];
		prefb[i] = prefb[i - 1] + b;
	}
	ll sumb = 0;
	for (int i = 1; i <= N; i++){
		ll rem = tla[i] - prefa[i];
		int mxid = upper_bound(prefb, prefb + M + 1, rem) - prefb - 1;
		if (mxid >= 0) pts[i].push_back({mxid, pta[i]});
	}
	for (int i = 1; i <= M; i++){
		ll rem = tlb[i] - prefb[i];
		int mxid = upper_bound(prefa, prefa + N + 1, rem) - prefa - 1;
		if (mxid >= 0){
			sumb += ptb[i];
			pts[mxid + 1].push_back({i - 1, -ptb[i]});
		}
	}
	node *root = new node(0, M);
	for (int i = 1; i <= N; i++){
		sort(pts[i].begin(), pts[i].end());
		for (auto [id, pt] : pts[i]) root->uadd(0, id, pt);
		for (auto [id, pt] : pts[i]){
			if (id == M) continue;
			ll v = root->query(id);
			int rb = root->search(id + 1, M, v);
			if (rb != id) root->uset(id + 1, rb, v);
		}
	}
	cout << sumb + root->query(M);
}

• 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