oj.uz

Submission #768094

# Submission time Handle Problem Language Result Execution time Memory
768094 2023-06-27T12:57:36 Z qwerasdfzxcl Two Dishes (JOI19_dishes) C++17
49 / 100
 500 ms 94044 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr ll INF = 4e18;

struct Foo{
	ll a, b;
	bool id;

	Foo(){}

	ll calc(ll x){return max(a, x) + b;}

	void operator += (const Foo &F){
		if (!id) {*this = F; return;}

		a = (a+b > F.a)?a:(F.a - b);
		b += F.b;
	}
};

struct Seg{
	ll ans[1101000];
	Foo lazy[2202000];
	
	void propagate(int i, int l, int r){
		if (!lazy[i].id) return;

		if (l==r) ans[l] = lazy[i].calc(ans[l]);
		else{
			lazy[i<<1] += lazy[i];
			lazy[i<<1|1] += lazy[i]; 
		}

		lazy[i].id = 0;
	}

	void add(int i, int l, int r, int s, int e, int x){
		propagate(i, l, r);
		if (r<s || e<l) return;
		if (s<=l && r<=e){
			lazy[i].a = -INF, lazy[i].b = x, lazy[i].id = 1;
			propagate(i, l, r);
			return;
		}

		int m = (l+r)>>1;
		add(i<<1, l, m, s, e, x); add(i<<1|1, m+1, r, s, e, x);
	}

	void max(int i, int l, int r, int s, int e, int x){
		propagate(i, l, r);
		if (r<s || e<l) return;
		if (s<=l && r<=e){
			lazy[i].a = x, lazy[i].b = 0, lazy[i].id = 1;
			propagate(i, l, r);
			return;
		}

		int m = (l+r)>>1;
		max(i<<1, l, m, s, e, x); max(i<<1|1, m+1, r, s, e, x);
	}

	ll query(int i, int l, int r, int p){
		propagate(i, l, r);
		if (l==r) return ans[l];

		int m = (l+r)>>1;
		if (p<=m) return query(i<<1, l, m, p);
		return query(i<<1|1, m+1, r, p);
	}
}tree;

int n, m;
int A[1001000], B[1001000], P[1001000], Q[1001000], mxA[1001000], mxB[1001000];
ll S[1001000], T[1001000], sumA[1001000], sumB[1001000], ans;
vector<pair<int, int>> lowerQ[1001000], upperQ[1001000];

void init(){
	for (int i=1;i<=n;i++) sumA[i] = sumA[i-1] + A[i];
	for (int i=1;i<=m;i++) sumB[i] = sumB[i-1] + B[i];
 
	for (int i=1;i<=n;i++){
		mxB[i] = upper_bound(sumB, sumB+m+1, S[i] - sumA[i]) - sumB - 1;

		if (mxB[i] >= 0) lowerQ[i-1].emplace_back(mxB[i], P[i]);
	}
	for (int i=1;i<=m;i++){
		mxA[i] = upper_bound(sumA, sumA+n+1, T[i] - sumB[i]) - sumA - 1;

		if (mxA[i]==n) ans += Q[i];
		else if (mxA[i] >= 0) upperQ[mxA[i]].emplace_back(i, Q[i]);
	}

	for (int i=0;i<n;i++){
		sort(lowerQ[i].begin(), lowerQ[i].end(), greater<pair<int, int>>());
		sort(upperQ[i].begin(), upperQ[i].end());
	}

}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(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];
 
	init();
 
	for (int x=0;x<n;x++){
		for (auto &[y, val]:upperQ[x]) tree.add(1, 0, m, y, m, val);
		for (auto &[y, val]:lowerQ[x]){
			tree.add(1, 0, m, 0, y, val);
			tree.max(1, 0, m, y+1, m, tree.query(1, 0, m, y));
		}
	}
 
	printf("%lld\n", tree.query(1, 0, m, m) + ans);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 89076 KB Output is correct
2 Incorrect 286 ms 94044 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47316 KB Output is correct
2 Correct 27 ms 47412 KB Output is correct
3 Correct 28 ms 47388 KB Output is correct
4 Correct 26 ms 47316 KB Output is correct
5 Correct 26 ms 47316 KB Output is correct
6 Correct 25 ms 47336 KB Output is correct
7 Correct 29 ms 47416 KB Output is correct
8 Correct 26 ms 47380 KB Output is correct
9 Correct 27 ms 47416 KB Output is correct
10 Correct 27 ms 47316 KB Output is correct
11 Correct 26 ms 47356 KB Output is correct
12 Correct 28 ms 47328 KB Output is correct
13 Correct 26 ms 47408 KB Output is correct
14 Correct 26 ms 47316 KB Output is correct
15 Correct 28 ms 47356 KB Output is correct
16 Correct 27 ms 47316 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47316 KB Output is correct
2 Correct 27 ms 47412 KB Output is correct
3 Correct 28 ms 47388 KB Output is correct
4 Correct 26 ms 47316 KB Output is correct
5 Correct 26 ms 47316 KB Output is correct
6 Correct 25 ms 47336 KB Output is correct
7 Correct 29 ms 47416 KB Output is correct
8 Correct 26 ms 47380 KB Output is correct
9 Correct 27 ms 47416 KB Output is correct
10 Correct 27 ms 47316 KB Output is correct
11 Correct 26 ms 47356 KB Output is correct
12 Correct 28 ms 47328 KB Output is correct
13 Correct 26 ms 47408 KB Output is correct
14 Correct 26 ms 47316 KB Output is correct
15 Correct 28 ms 47356 KB Output is correct
16 Correct 27 ms 47316 KB Output is correct
17 Correct 27 ms 47676 KB Output is correct
18 Correct 31 ms 47744 KB Output is correct
19 Correct 30 ms 47804 KB Output is correct
20 Correct 31 ms 47808 KB Output is correct
21 Correct 28 ms 47732 KB Output is correct
22 Correct 28 ms 47668 KB Output is correct
23 Correct 35 ms 47700 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47316 KB Output is correct
2 Correct 27 ms 47412 KB Output is correct
3 Correct 28 ms 47388 KB Output is correct
4 Correct 26 ms 47316 KB Output is correct
5 Correct 26 ms 47316 KB Output is correct
6 Correct 25 ms 47336 KB Output is correct
7 Correct 29 ms 47416 KB Output is correct
8 Correct 26 ms 47380 KB Output is correct
9 Correct 27 ms 47416 KB Output is correct
10 Correct 27 ms 47316 KB Output is correct
11 Correct 26 ms 47356 KB Output is correct
12 Correct 28 ms 47328 KB Output is correct
13 Correct 26 ms 47408 KB Output is correct
14 Correct 26 ms 47316 KB Output is correct
15 Correct 28 ms 47356 KB Output is correct
16 Correct 27 ms 47316 KB Output is correct
17 Correct 27 ms 47676 KB Output is correct
18 Correct 31 ms 47744 KB Output is correct
19 Correct 30 ms 47804 KB Output is correct
20 Correct 31 ms 47808 KB Output is correct
21 Correct 28 ms 47732 KB Output is correct
22 Correct 28 ms 47668 KB Output is correct
23 Correct 35 ms 47700 KB Output is correct
24 Correct 227 ms 75260 KB Output is correct
25 Correct 219 ms 87656 KB Output is correct
26 Correct 236 ms 89060 KB Output is correct
27 Correct 211 ms 92308 KB Output is correct
28 Correct 260 ms 89948 KB Output is correct
29 Correct 157 ms 75980 KB Output is correct
30 Correct 500 ms 93176 KB Output is correct
31 Correct 98 ms 72920 KB Output is correct
32 Correct 86 ms 64396 KB Output is correct
33 Correct 330 ms 88040 KB Output is correct
34 Correct 447 ms 91728 KB Output is correct
35 Correct 490 ms 86888 KB Output is correct
36 Correct 475 ms 86728 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47316 KB Output is correct
2 Correct 27 ms 47412 KB Output is correct
3 Correct 28 ms 47388 KB Output is correct
4 Correct 26 ms 47316 KB Output is correct
5 Correct 26 ms 47316 KB Output is correct
6 Correct 25 ms 47336 KB Output is correct
7 Correct 29 ms 47416 KB Output is correct
8 Correct 26 ms 47380 KB Output is correct
9 Correct 27 ms 47416 KB Output is correct
10 Correct 27 ms 47316 KB Output is correct
11 Correct 26 ms 47356 KB Output is correct
12 Correct 28 ms 47328 KB Output is correct
13 Correct 26 ms 47408 KB Output is correct
14 Correct 26 ms 47316 KB Output is correct
15 Correct 28 ms 47356 KB Output is correct
16 Correct 27 ms 47316 KB Output is correct
17 Correct 27 ms 47676 KB Output is correct
18 Correct 31 ms 47744 KB Output is correct
19 Correct 30 ms 47804 KB Output is correct
20 Correct 31 ms 47808 KB Output is correct
21 Correct 28 ms 47732 KB Output is correct
22 Correct 28 ms 47668 KB Output is correct
23 Correct 35 ms 47700 KB Output is correct
24 Correct 227 ms 75260 KB Output is correct
25 Correct 219 ms 87656 KB Output is correct
26 Correct 236 ms 89060 KB Output is correct
27 Correct 211 ms 92308 KB Output is correct
28 Correct 260 ms 89948 KB Output is correct
29 Correct 157 ms 75980 KB Output is correct
30 Correct 500 ms 93176 KB Output is correct
31 Correct 98 ms 72920 KB Output is correct
32 Correct 86 ms 64396 KB Output is correct
33 Correct 330 ms 88040 KB Output is correct
34 Correct 447 ms 91728 KB Output is correct
35 Correct 490 ms 86888 KB Output is correct
36 Correct 475 ms 86728 KB Output is correct
37 Incorrect 242 ms 92156 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47316 KB Output is correct
2 Correct 27 ms 47412 KB Output is correct
3 Correct 28 ms 47388 KB Output is correct
4 Correct 26 ms 47316 KB Output is correct
5 Correct 26 ms 47316 KB Output is correct
6 Correct 25 ms 47336 KB Output is correct
7 Correct 29 ms 47416 KB Output is correct
8 Correct 26 ms 47380 KB Output is correct
9 Correct 27 ms 47416 KB Output is correct
10 Correct 27 ms 47316 KB Output is correct
11 Correct 26 ms 47356 KB Output is correct
12 Correct 28 ms 47328 KB Output is correct
13 Correct 26 ms 47408 KB Output is correct
14 Correct 26 ms 47316 KB Output is correct
15 Correct 28 ms 47356 KB Output is correct
16 Correct 27 ms 47316 KB Output is correct
17 Correct 27 ms 47676 KB Output is correct
18 Correct 31 ms 47744 KB Output is correct
19 Correct 30 ms 47804 KB Output is correct
20 Correct 31 ms 47808 KB Output is correct
21 Correct 28 ms 47732 KB Output is correct
22 Correct 28 ms 47668 KB Output is correct
23 Correct 35 ms 47700 KB Output is correct
24 Correct 227 ms 75260 KB Output is correct
25 Correct 219 ms 87656 KB Output is correct
26 Correct 236 ms 89060 KB Output is correct
27 Correct 211 ms 92308 KB Output is correct
28 Correct 260 ms 89948 KB Output is correct
29 Correct 157 ms 75980 KB Output is correct
30 Correct 500 ms 93176 KB Output is correct
31 Correct 98 ms 72920 KB Output is correct
32 Correct 86 ms 64396 KB Output is correct
33 Correct 330 ms 88040 KB Output is correct
34 Correct 447 ms 91728 KB Output is correct
35 Correct 490 ms 86888 KB Output is correct
36 Correct 475 ms 86728 KB Output is correct
37 Incorrect 242 ms 92156 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 89076 KB Output is correct
2 Incorrect 286 ms 94044 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 89076 KB Output is correct
2 Incorrect 286 ms 94044 KB Output isn't correct
3 Halted 0 ms 0 KB -