oj.uz

Submission #721311

# Submission time Handle Problem Language Result Execution time Memory
721311 2023-04-10T16:29:09 Z lukameladze Two Dishes (JOI19_dishes) C++14
5 / 100
 553 ms 63748 KB 
# 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;	
}
 
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] 
		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];
	//	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({0, 0}); 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);
		}
	}
	int ans1 = -inf;
	for (int i = 1; i <= m; i++) {
		ans1 = max(ans1, getans(1,0,m, i));
	}
	cout<<ans + ans1<<"\n";
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 62616 KB Output is correct
2 Correct 553 ms 63748 KB Output is correct
3 Correct 348 ms 63380 KB Output is correct
4 Correct 458 ms 56672 KB Output is correct
5 Correct 13 ms 23828 KB Output is correct
6 Correct 495 ms 63044 KB Output is correct
7 Correct 137 ms 41152 KB Output is correct
8 Correct 133 ms 45868 KB Output is correct
9 Correct 354 ms 63460 KB Output is correct
10 Correct 523 ms 60364 KB Output is correct
11 Correct 313 ms 63396 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 62616 KB Output is correct
2 Correct 553 ms 63748 KB Output is correct
3 Correct 348 ms 63380 KB Output is correct
4 Correct 458 ms 56672 KB Output is correct
5 Correct 13 ms 23828 KB Output is correct
6 Correct 495 ms 63044 KB Output is correct
7 Correct 137 ms 41152 KB Output is correct
8 Correct 133 ms 45868 KB Output is correct
9 Correct 354 ms 63460 KB Output is correct
10 Correct 523 ms 60364 KB Output is correct
11 Correct 313 ms 63396 KB Output is correct
12 Incorrect 13 ms 23892 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 62616 KB Output is correct
2 Correct 553 ms 63748 KB Output is correct
3 Correct 348 ms 63380 KB Output is correct
4 Correct 458 ms 56672 KB Output is correct
5 Correct 13 ms 23828 KB Output is correct
6 Correct 495 ms 63044 KB Output is correct
7 Correct 137 ms 41152 KB Output is correct
8 Correct 133 ms 45868 KB Output is correct
9 Correct 354 ms 63460 KB Output is correct
10 Correct 523 ms 60364 KB Output is correct
11 Correct 313 ms 63396 KB Output is correct
12 Incorrect 13 ms 23892 KB Output isn't correct
13 Halted 0 ms 0 KB -