Submission #1221377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221377		PenguinsAreCute	Two Dishes (JOI19_dishes)	C++17	100 / 100	3622 ms	188280 KiB

dishes

#include <bits/stdc++.h>
using namespace std;
struct seg {
	vector<long long> val, lazy;
	int n, h;
	seg(int _n): n(_n), h(32-__builtin_clz(_n)), val(2*_n,0), lazy(_n,0) {}
	void app(int x, long long k) {
		val[x] += k;
		if(x < n)
			lazy[x] += k;
	}
	void calc(int x) {
		val[x] = max(val[x<<1],val[x<<1|1]) + lazy[x];
	}
	void push(int x) {
		for(int i=h;i;i--) {
			int y = (x >> i);
			app(y<<1,lazy[y]);
			app(y<<1|1,lazy[y]);
			lazy[y] = 0;
		}
	}
	void build(int x) {
		while(x>>=1)
			calc(x);
	}
	void up(int l, int r, long long x) {
		int l0 = (l+=n);
		int r0 = (r+=n);
		push(l0);
		push(r0);
		for(r++;l<r;l>>=1,r>>=1) {
			if(l&1)
				app(l++,x);
			if(r&1)
				app(--r,x);
		}
		build(l0);
		build(r0);
	}
	long long qry(int l, int r) {
		push(l+=n);
		push(r+=n);
		long long ans = 0;
		for(r++;l<r;l>>=1,r>>=1) {
			if(l&1)
				ans=max(ans,val[l++]);
			if(r&1)
				ans=max(ans,val[--r]);
		}
		return ans;
	}
};
int main() {
	int n, m;
	cin >> n >> m;
	long long a[n], s[n], b[m], t[m];
	int p[n], q[m];
	for(int i=0,trash;i<n;i++)
		cin >> a[i] >> s[i] >> p[i];
	for(int i=0,trash;i<m;i++)
		cin >> b[i] >> t[i] >> q[i];
	long long pa[n+1], pb[m+1];
	pa[0] = pb[0] = 0;
	partial_sum(a,a+n,pa+1);
	partial_sum(b,b+m,pb+1);
	long long ans = 0;
	vector<pair<int,int>> out[n], in[n];
	for(int i=0;i<n;i++) {
		s[i] = upper_bound(pb,pb+m+1,s[i]-pa[i+1])-pb-1;
		if(s[i] == m) {
			s[i] = -1;
			ans += p[i];
		} else if((~s[i]) && p[i] >= 0)
			out[i].push_back({s[i],p[i]});
		else if(~s[i]) {
			ans += p[i];
			in[i].push_back({s[i],-p[i]});
		}
	}
	for(int i=0;i<m;i++) {
		t[i] = upper_bound(pa,pa+n+1,t[i]-pb[i+1])-pa-1;
		if(t[i] == n) {
			t[i] = -1;
			ans+=q[i];
		} else if((~t[i]) && q[i] >= 0)
			in[t[i]].push_back({i,q[i]});
		else if(~t[i]) {
			ans += q[i];
			out[t[i]].push_back({i,-q[i]});
		}
	}
	seg dp(m+1);
	for(int i=n;i--;) {
		for(auto [j, v]: out[i]) {
			dp.up(j,j,dp.qry(j,m)+v-dp.qry(j,j));
			dp.up(0,j-1,v);
		}
		for(auto [j, v]: in[i])
			dp.up(j+1,m,v);
	}
	cout << ans + dp.qry(0,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