oj.uz

Submission #871547

# Submission time Handle Problem Language Result Execution time Memory
871547 2023-11-11T05:27:18 Z qthang2k11 Two Dishes (JOI19_dishes) C++17
5 / 100
 326 ms 165712 KB 
// [+]
#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) {
		// cerr << "update_add(" << x << ", " << y << ", " << w << ")\n";
		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) {
		// cerr << "update_max(" << x << ", " << y << ", " << w << ")\n";
		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) {
		// cerr << "get(" << x << ") = " << get(x, 1, 1, M) << '\n';
		return get(x, 1, 1, M);
	}
} seg;

// ll debug[1000][1000];

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];
		
		// cerr << "hihi " << i << ' ' << pos << '\n';
	}
	
	// cerr << "siu " << siu << '\n';
	
	node[n].emplace_back(m, 0);
	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;
		}
		
		// for (auto [j, val]: tmp)
			// debug[i][j] = val,
			// cerr << string(10, ' ') << "[" << i << ", " << j << "] = " << val << '\n';
		
		ll sum = 0;
		for (auto &elem: tmp) {
			elem.first++;
			sum += elem.second;
		}
		
		// cerr << "i = " << i << ", sum = " << sum << '\n';
		
		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;
			// cerr << L << ' ' << R << '\n';
			
			seg.update_add(L, R, sum);
			pre_max = max(pre_max, seg.get(R));
			seg.update_max(L, R, pre_max);
			
			sum -= tmp[i].second;
		}
		
		// ll pre_max = LLONG_MIN;
		// for (const auto &elem: tmp) {
			// int pos = upper_bound(arr.begin(), arr.end(), elem.first) - arr.begin();
// 			
			// dp[pos] = max(dp[pos] + sum, pre_max);
// 			
			// pre_max = max(pre_max, dp[pos]);
			// sum -= elem.second;
		// }
		
		// cerr << "at i = " << i << '\n';
		// for (const auto &elem: tmp)
			// cerr << elem.first << ' ' << elem.second << '\n';
// 		
		// for (int j = 1; j <= M; j++)
			// fprintf(stderr, "dp[%d][%d] = %lld\n", i, j - 1, seg.get(j));
		// cerr << '\n';
	}
	
	// cerr << "siu = " << siu << '\n';
	
	cout << seg.get(M) + siu;
	
	// for (int i = m; i >= 0; i--)
		// for (int j = 1; j <= n; j++)
			// cerr << debug[j][i] << " \n"[j == n];
	
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 165708 KB Output is correct
2 Correct 314 ms 165712 KB Output is correct
3 Correct 174 ms 160988 KB Output is correct
4 Correct 254 ms 163564 KB Output is correct
5 Correct 21 ms 131920 KB Output is correct
6 Correct 281 ms 164692 KB Output is correct
7 Correct 74 ms 140624 KB Output is correct
8 Correct 96 ms 152392 KB Output is correct
9 Correct 174 ms 161860 KB Output is correct
10 Correct 282 ms 161456 KB Output is correct
11 Correct 145 ms 155216 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 131920 KB Output is correct
2 Correct 20 ms 131932 KB Output is correct
3 Correct 20 ms 131880 KB Output is correct
4 Correct 20 ms 131932 KB Output is correct
5 Correct 21 ms 132044 KB Output is correct
6 Correct 20 ms 131932 KB Output is correct
7 Incorrect 20 ms 131924 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 131920 KB Output is correct
2 Correct 20 ms 131932 KB Output is correct
3 Correct 20 ms 131880 KB Output is correct
4 Correct 20 ms 131932 KB Output is correct
5 Correct 21 ms 132044 KB Output is correct
6 Correct 20 ms 131932 KB Output is correct
7 Incorrect 20 ms 131924 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 131920 KB Output is correct
2 Correct 20 ms 131932 KB Output is correct
3 Correct 20 ms 131880 KB Output is correct
4 Correct 20 ms 131932 KB Output is correct
5 Correct 21 ms 132044 KB Output is correct
6 Correct 20 ms 131932 KB Output is correct
7 Incorrect 20 ms 131924 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 131920 KB Output is correct
2 Correct 20 ms 131932 KB Output is correct
3 Correct 20 ms 131880 KB Output is correct
4 Correct 20 ms 131932 KB Output is correct
5 Correct 21 ms 132044 KB Output is correct
6 Correct 20 ms 131932 KB Output is correct
7 Incorrect 20 ms 131924 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 131920 KB Output is correct
2 Correct 20 ms 131932 KB Output is correct
3 Correct 20 ms 131880 KB Output is correct
4 Correct 20 ms 131932 KB Output is correct
5 Correct 21 ms 132044 KB Output is correct
6 Correct 20 ms 131932 KB Output is correct
7 Incorrect 20 ms 131924 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 165708 KB Output is correct
2 Correct 314 ms 165712 KB Output is correct
3 Correct 174 ms 160988 KB Output is correct
4 Correct 254 ms 163564 KB Output is correct
5 Correct 21 ms 131920 KB Output is correct
6 Correct 281 ms 164692 KB Output is correct
7 Correct 74 ms 140624 KB Output is correct
8 Correct 96 ms 152392 KB Output is correct
9 Correct 174 ms 161860 KB Output is correct
10 Correct 282 ms 161456 KB Output is correct
11 Correct 145 ms 155216 KB Output is correct
12 Correct 20 ms 131920 KB Output is correct
13 Correct 20 ms 131932 KB Output is correct
14 Correct 20 ms 131880 KB Output is correct
15 Correct 20 ms 131932 KB Output is correct
16 Correct 21 ms 132044 KB Output is correct
17 Correct 20 ms 131932 KB Output is correct
18 Incorrect 20 ms 131924 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 165708 KB Output is correct
2 Correct 314 ms 165712 KB Output is correct
3 Correct 174 ms 160988 KB Output is correct
4 Correct 254 ms 163564 KB Output is correct
5 Correct 21 ms 131920 KB Output is correct
6 Correct 281 ms 164692 KB Output is correct
7 Correct 74 ms 140624 KB Output is correct
8 Correct 96 ms 152392 KB Output is correct
9 Correct 174 ms 161860 KB Output is correct
10 Correct 282 ms 161456 KB Output is correct
11 Correct 145 ms 155216 KB Output is correct
12 Correct 20 ms 131920 KB Output is correct
13 Correct 20 ms 131932 KB Output is correct
14 Correct 20 ms 131880 KB Output is correct
15 Correct 20 ms 131932 KB Output is correct
16 Correct 21 ms 132044 KB Output is correct
17 Correct 20 ms 131932 KB Output is correct
18 Incorrect 20 ms 131924 KB Output isn't correct
19 Halted 0 ms 0 KB -