Submission #721337

#	Time	Username	Problem	Language	Result	Execution time	Memory
721337		lukameladze	Two Dishes (JOI19_dishes)	C++14	5 / 100	550 ms	60492 KiB

dishes

# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
 #define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 1e6 + 5, inf = 1e17;
int n,m,a[N],b[N],s[N],p[N],q[N],t[N],x[N],y[N],ans;
 
 
int maxim[4 * N], lazy[4 * N];
vector <pii> v[N];
int merge(int a, int b) {
	return max(a, b);
}
void push(int node, int le, int ri) {
	if (le == ri) {
		maxim[node] += lazy[node];
		lazy[node] = 0;
		return ;
	}
	maxim[2 * node] = max(maxim[2 * node], maxim[node]);
	maxim[2 * node + 1] = max(maxim[2 * node + 1], maxim[node]);
	maxim[node] += lazy[node];
	lazy[2 * node] += lazy[node];
	lazy[2 * node + 1] += lazy[node];
	
	lazy[node] = 0;	
	maxim[node] = -inf;
}
 
void build(int node, int le, int ri) {
	if (le == ri) {
		maxim[node] = 0;
		return ;
	} else maxim[node] = -inf;
	int mid = (le + ri) / 2;
	build(2 * node, le, mid);
	build(2 * node + 1, mid + 1, ri);
}
void update(int node, int le, int ri, int start, int end, int val) {
	push(node, le, ri);
	if (le > end || ri < start || start > end) return ;
	if (le >= start && ri <= end) {
		lazy[node] += val;
		push(node, le, ri);
		return ;
	}
	int mid = (le + ri) / 2;
	update(2 * node, le, mid, start, end, val);
	update(2 * node + 1, mid + 1, ri, start, end, val);
}
void maximize(int node, int le, int ri, int start, int end, int val) {
	push(node, le, ri);
	if (le > end || ri < start || start > end) return ;
	if (le >= start && ri <= end) {
		//cout<<node<<"      "<<val<<"\n";
		maxim[node] = max(maxim[node], val);
		push(node, le, ri);
		return ;
	}
	int mid = (le + ri) / 2;
	maximize(2 * node, le, mid,start,end,val);
	maximize(2 * node + 1, mid + 1, ri, start, end, val);
}
int getans(int node, int le, int ri, int idx) {
	push(node, le, ri);
	if (le > idx || ri < idx) return -inf;
	if (le == ri) {
		return maxim[node];	
	}
	int mid = (le + ri) / 2;
	return merge(getans(2 * node, le, mid, idx), getans(2 * node + 1, mid + 1, ri, idx));
}
/*
void prnt(int node, int le, int ri) {
//	cout<<node<<" "<<le<<" "<<ri<<"   "<<maxim[node]<<" "<<lazy[node]<<"\n";
	if (le == ri) return ; 
	int mid = (le + ri) / 2;
	prnt(2 * node, le, mid);
	prnt(2 * node + 1, mid + 1, ri);
}
 */
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for (int i = 1; i <= n; i++) {
		cin>>a[i]>>s[i]>>p[i];
		a[i] += a[i - 1];
	}
	for (int i = 1; i <= m; i++) {
		cin>>b[i]>>t[i]>>q[i];
		b[i] += b[i - 1];
	}
	for (int i = 1; i <= n; i++) {
		if (a[i] > s[i]) continue;
		x[i] = upper_bound(b, b + m + 1, s[i] - a[i]) - b; // x[i] = minimum index such that pra[i] + prb[idx] > s[i] 
		if (x[i] > m) {
		    ans += p[i]; continue;
		}
		v[i].pb({x[i], p[i]});
	//	cout<<i<<"   "<<x[i]<<"\n";
	}
	build(1, 0, m);
	for (int i = 1; i <= m; i++) {
		if (b[i] > t[i]) continue;
		y[i] = upper_bound(a, a + n + 1, t[i] - b[i]) - a; // y[i] = minimum index such that prb[i] + pra[idx] > t[i];
		if (y[i] > n) {
		    ans += q[i]; continue; 
		}
	//	cout<<y[i]<<" --   "<<i<<"\n";
		ans += q[i];
		v[y[i]].pb({i, -q[i]});
	}
	for (int i = 1; i <= n; i++) {
		v[i].pb({m + 1, 0});
		sort(v[i].begin(), v[i].end());
		for (pii sth : v[i]) {
			int j = sth.f; int cost = sth.s; 
			update(1, 0, m, 0, j - 1, cost);
		}
		// prefix maximization
		for (pii sth : v[i]) {
			int j = sth.f; int cost = sth.s;
			int x = getans(1,0,m, j - 1);
			maximize(1,0,m,j, m,x);
		}
	/*	for (int i = 0; i <= m; i++) {
		    cout<<getans(1, 0, m, i)<<" ";
		}
		cout<<"\n";*/
	}
	int ans1 = -inf;
	for (int i = 1; i <= m; i++) {
		ans1 = max(ans1, getans(1,0,m, i));
	}
	cout<<ans + ans1<<"\n";
}
 
 

Compilation message (stderr)

dishes.cpp:85:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   85 | main() {
      | ^~~~
dishes.cpp: In function 'int main()':
dishes.cpp:125:23: warning: unused variable 'cost' [-Wunused-variable]
  125 |    int j = sth.f; int cost = sth.s;
      |                       ^~~~

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