oj.uz

Submission #767801

# Submission time Handle Problem Language Result Execution time Memory
767801 2023-06-27T07:40:41 Z qwerasdfzxcl Two Dishes (JOI19_dishes) C++17
74 / 100
 8135 ms 282884 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct Block{
	int s, e;
	ll a0;

	Block(){}
	Block(int _s, int _e, ll _a0): s(_s), e(_e), a0(_a0) {}
};

vector<Block> buf;

struct Seg{
	ll treeV[2202000];
	int treeB[2202000];

	ll lazyBadd[2202000], lazyBidx[2202000];

	void init(int i, int l, int r, ll a[]){
		lazyBadd[i] = 0, lazyBidx[i] = -1;
		if (l==r){
			treeV[i] = a[l];
			treeB[i] = 1;
			return;
		}

		int m = (l+r)>>1;
		init(i<<1, l, m, a); init(i<<1|1, m+1, r, a);
		treeV[i] = treeV[i<<1] + treeV[i<<1|1];
	}

	void propagate(int i, int l, int r){
		if (l==r){
			if (lazyBidx[i]!=-1) treeB[i] = lazyBidx[i];
			if (buf[treeB[i]].s==l) buf[treeB[i]].a0 += lazyBadd[i];
		}

		else{
			if (lazyBidx[i]!=-1){
				lazyBidx[i<<1] = lazyBidx[i];
				lazyBadd[i<<1] = 0;
				lazyBidx[i<<1|1] = lazyBidx[i];
				lazyBadd[i<<1|1] = 0;
			}

			lazyBadd[i<<1] += lazyBadd[i];
			lazyBadd[i<<1|1] += lazyBadd[i];
		}

		lazyBidx[i] = -1;
		lazyBadd[i] = 0;
	}

	void update(int i, int l, int r, int p, int v){
		propagate(i, l, r);
		if (r<p || p<l) return;
		if (l==r){
			treeV[i] = v;
			return;
		}

		int m = (l+r)>>1;
		update(i<<1, l, m, p, v); update(i<<1|1, m+1, r, p, v);
		treeV[i] = treeV[i<<1] + treeV[i<<1|1];
	}

	void updateB(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){
			lazyBidx[i] = x;
			propagate(i, l, r);
			return;
		}

		int m = (l+r)>>1;
		updateB(i<<1, l, m, s, e, x); updateB(i<<1|1, m+1, r, s, e, x);
		treeV[i] = treeV[i<<1] + treeV[i<<1|1];
	}

	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){
			lazyBadd[i] += x;
			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);
		treeV[i] = treeV[i<<1] + treeV[i<<1|1];
	}

	ll queryV(int i, int l, int r, int s, int e){
		propagate(i, l, r);
		if (r<s || e<l) return 0;
		if (s<=l && r<=e) return treeV[i];

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

	int queryB(int i, int l, int r, int p){
		propagate(i, l, r);
		if (r<p || p<l) return 0;
		if (l==r) return treeB[i];

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

int n, m;
ll A[1001000], B[1001000], S[1001000], T[1001000], P[1001000], Q[1001000];
ll sumA[1001000], sumB[1001000], W[1001000], mxA[1001000], mxB[1001000];
vector<int> Vp[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]==-1) W[i] = 0;
		else{
			W[i] = P[i];
			Vp[mxB[i]].push_back(i);
		}
	}
	for (int i=1;i<=m;i++){
		mxA[i] = upper_bound(sumA, sumA+n+1, T[i] - sumB[i]) - sumA - 1;
	}

	// printf("mxB: ");
	// for (int i=1;i<=n;i++) printf("%lld ", mxB[i]);
	// printf("\nmxA: ");
	// for (int i=1;i<=m;i++) printf("%lld ", mxA[i]);
	// printf("\nW: ");
	// for (int i=1;i<=n;i++) printf("%lld ", W[i]);
	// printf("\n");

	buf.emplace_back();
	buf.emplace_back(0, n, 0);
	tree.init(1, 0, n, W);
}


int getidx(int x){
	int ret = tree.queryB(1, 0, n, x);
	tree.queryB(1, 0, n, buf[ret].s);
	return ret;
}

ll calc(int x){
	int idx = getidx(x);
	return buf[idx].a0 + tree.queryV(1, 0, n, buf[idx].s+1, x);
}

void split(int x){
	int idx = getidx(x);
	
	if (buf[idx].s==x) return;

	buf.emplace_back(buf[idx].s, x-1, buf[idx].a0);
	buf[idx].a0 = calc(x);
	buf[idx].s = x;

	tree.updateB(1, 0, n, buf.back().s, x-1, (int)buf.size()-1);
}

void merge(int cur, int nxt){
	buf[cur].e = buf[nxt].e;
	tree.updateB(1, 0, n, buf[nxt].s, buf[nxt].e, cur);
}

void refresh(int x){
	int cur = getidx(x);
	while(true){
		if (buf[cur].e==n) return;
		
		int nxt = getidx(buf[cur].e+1);
		// printf("cur: (%d, %d, %lld) / nxt: (%d, %d, %lld) / w = %lld\n", buf[cur].s, buf[cur].e, buf[cur].a0, buf[nxt].s, buf[nxt].e, buf[nxt].a0, tree.queryV(1, 0, n, buf[cur].e+1, buf[cur].e+1));
		if (calc(buf[cur].e) + tree.queryV(1, 0, n, buf[cur].e+1, buf[cur].e+1) >= buf[nxt].a0) merge(cur, nxt);
		else return;
	}
}

void updateXp(int x, int w){ // between x-1 and x
	// printf("updateXp: %d\n", x);
	split(x);
	tree.update(1, 0, n, x, w);
}

void updateYp(int x, int q){
	// printf("updateYp: %d %d\n", x, q);
	tree.add(1, 0, n, 0, x, q);
	refresh(x);
}


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 y=1;y<=m;y++){
		for (auto &x:Vp[y-1]) updateXp(x, 0);
		
		if (Q[y] > 0 && mxA[y] >= 0) updateYp(mxA[y], Q[y]);
		// else if (Q[y] < 0) updateYm(Q[y]);

		// for (auto &x:Vm[y]) updateXm(x);
		// for (int x=0;x<=n;x++) printf("%lld ", calc(x));
		// printf("\n");
	}

	printf("%lld\n", calc(n));
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 63032 KB Output is correct
2 Correct 655 ms 76644 KB Output is correct
3 Correct 177 ms 69192 KB Output is correct
4 Correct 526 ms 74324 KB Output is correct
5 Correct 13 ms 23892 KB Output is correct
6 Correct 711 ms 75268 KB Output is correct
7 Correct 70 ms 38568 KB Output is correct
8 Correct 74 ms 54976 KB Output is correct
9 Correct 185 ms 70360 KB Output is correct
10 Correct 893 ms 72888 KB Output is correct
11 Correct 147 ms 63688 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23816 KB Output is correct
2 Correct 12 ms 23892 KB Output is correct
3 Correct 12 ms 23832 KB Output is correct
4 Correct 13 ms 23840 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 13 ms 23888 KB Output is correct
7 Correct 12 ms 23936 KB Output is correct
8 Correct 14 ms 23832 KB Output is correct
9 Correct 12 ms 23864 KB Output is correct
10 Correct 12 ms 23948 KB Output is correct
11 Correct 12 ms 23892 KB Output is correct
12 Correct 12 ms 23892 KB Output is correct
13 Correct 12 ms 23892 KB Output is correct
14 Correct 12 ms 23892 KB Output is correct
15 Correct 12 ms 23832 KB Output is correct
16 Correct 12 ms 23876 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23816 KB Output is correct
2 Correct 12 ms 23892 KB Output is correct
3 Correct 12 ms 23832 KB Output is correct
4 Correct 13 ms 23840 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 13 ms 23888 KB Output is correct
7 Correct 12 ms 23936 KB Output is correct
8 Correct 14 ms 23832 KB Output is correct
9 Correct 12 ms 23864 KB Output is correct
10 Correct 12 ms 23948 KB Output is correct
11 Correct 12 ms 23892 KB Output is correct
12 Correct 12 ms 23892 KB Output is correct
13 Correct 12 ms 23892 KB Output is correct
14 Correct 12 ms 23892 KB Output is correct
15 Correct 12 ms 23832 KB Output is correct
16 Correct 12 ms 23876 KB Output is correct
17 Correct 14 ms 24360 KB Output is correct
18 Correct 13 ms 24324 KB Output is correct
19 Correct 19 ms 24404 KB Output is correct
20 Correct 16 ms 24348 KB Output is correct
21 Correct 16 ms 24356 KB Output is correct
22 Correct 19 ms 24336 KB Output is correct
23 Correct 18 ms 24276 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23816 KB Output is correct
2 Correct 12 ms 23892 KB Output is correct
3 Correct 12 ms 23832 KB Output is correct
4 Correct 13 ms 23840 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 13 ms 23888 KB Output is correct
7 Correct 12 ms 23936 KB Output is correct
8 Correct 14 ms 23832 KB Output is correct
9 Correct 12 ms 23864 KB Output is correct
10 Correct 12 ms 23948 KB Output is correct
11 Correct 12 ms 23892 KB Output is correct
12 Correct 12 ms 23892 KB Output is correct
13 Correct 12 ms 23892 KB Output is correct
14 Correct 12 ms 23892 KB Output is correct
15 Correct 12 ms 23832 KB Output is correct
16 Correct 12 ms 23876 KB Output is correct
17 Correct 14 ms 24360 KB Output is correct
18 Correct 13 ms 24324 KB Output is correct
19 Correct 19 ms 24404 KB Output is correct
20 Correct 16 ms 24348 KB Output is correct
21 Correct 16 ms 24356 KB Output is correct
22 Correct 19 ms 24336 KB Output is correct
23 Correct 18 ms 24276 KB Output is correct
24 Correct 349 ms 70584 KB Output is correct
25 Correct 203 ms 65980 KB Output is correct
26 Correct 375 ms 76184 KB Output is correct
27 Correct 213 ms 66164 KB Output is correct
28 Correct 442 ms 69000 KB Output is correct
29 Correct 167 ms 67168 KB Output is correct
30 Correct 1201 ms 73828 KB Output is correct
31 Correct 64 ms 36940 KB Output is correct
32 Correct 172 ms 55300 KB Output is correct
33 Correct 665 ms 69796 KB Output is correct
34 Correct 742 ms 71988 KB Output is correct
35 Correct 1233 ms 67424 KB Output is correct
36 Correct 1192 ms 67436 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23816 KB Output is correct
2 Correct 12 ms 23892 KB Output is correct
3 Correct 12 ms 23832 KB Output is correct
4 Correct 13 ms 23840 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 13 ms 23888 KB Output is correct
7 Correct 12 ms 23936 KB Output is correct
8 Correct 14 ms 23832 KB Output is correct
9 Correct 12 ms 23864 KB Output is correct
10 Correct 12 ms 23948 KB Output is correct
11 Correct 12 ms 23892 KB Output is correct
12 Correct 12 ms 23892 KB Output is correct
13 Correct 12 ms 23892 KB Output is correct
14 Correct 12 ms 23892 KB Output is correct
15 Correct 12 ms 23832 KB Output is correct
16 Correct 12 ms 23876 KB Output is correct
17 Correct 14 ms 24360 KB Output is correct
18 Correct 13 ms 24324 KB Output is correct
19 Correct 19 ms 24404 KB Output is correct
20 Correct 16 ms 24348 KB Output is correct
21 Correct 16 ms 24356 KB Output is correct
22 Correct 19 ms 24336 KB Output is correct
23 Correct 18 ms 24276 KB Output is correct
24 Correct 349 ms 70584 KB Output is correct
25 Correct 203 ms 65980 KB Output is correct
26 Correct 375 ms 76184 KB Output is correct
27 Correct 213 ms 66164 KB Output is correct
28 Correct 442 ms 69000 KB Output is correct
29 Correct 167 ms 67168 KB Output is correct
30 Correct 1201 ms 73828 KB Output is correct
31 Correct 64 ms 36940 KB Output is correct
32 Correct 172 ms 55300 KB Output is correct
33 Correct 665 ms 69796 KB Output is correct
34 Correct 742 ms 71988 KB Output is correct
35 Correct 1233 ms 67424 KB Output is correct
36 Correct 1192 ms 67436 KB Output is correct
37 Correct 439 ms 79136 KB Output is correct
38 Correct 231 ms 69208 KB Output is correct
39 Correct 980 ms 76664 KB Output is correct
40 Correct 933 ms 76548 KB Output is correct
41 Correct 12 ms 23892 KB Output is correct
42 Correct 1222 ms 76940 KB Output is correct
43 Correct 687 ms 72708 KB Output is correct
44 Correct 770 ms 74812 KB Output is correct
45 Correct 1228 ms 70524 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23816 KB Output is correct
2 Correct 12 ms 23892 KB Output is correct
3 Correct 12 ms 23832 KB Output is correct
4 Correct 13 ms 23840 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 13 ms 23888 KB Output is correct
7 Correct 12 ms 23936 KB Output is correct
8 Correct 14 ms 23832 KB Output is correct
9 Correct 12 ms 23864 KB Output is correct
10 Correct 12 ms 23948 KB Output is correct
11 Correct 12 ms 23892 KB Output is correct
12 Correct 12 ms 23892 KB Output is correct
13 Correct 12 ms 23892 KB Output is correct
14 Correct 12 ms 23892 KB Output is correct
15 Correct 12 ms 23832 KB Output is correct
16 Correct 12 ms 23876 KB Output is correct
17 Correct 14 ms 24360 KB Output is correct
18 Correct 13 ms 24324 KB Output is correct
19 Correct 19 ms 24404 KB Output is correct
20 Correct 16 ms 24348 KB Output is correct
21 Correct 16 ms 24356 KB Output is correct
22 Correct 19 ms 24336 KB Output is correct
23 Correct 18 ms 24276 KB Output is correct
24 Correct 349 ms 70584 KB Output is correct
25 Correct 203 ms 65980 KB Output is correct
26 Correct 375 ms 76184 KB Output is correct
27 Correct 213 ms 66164 KB Output is correct
28 Correct 442 ms 69000 KB Output is correct
29 Correct 167 ms 67168 KB Output is correct
30 Correct 1201 ms 73828 KB Output is correct
31 Correct 64 ms 36940 KB Output is correct
32 Correct 172 ms 55300 KB Output is correct
33 Correct 665 ms 69796 KB Output is correct
34 Correct 742 ms 71988 KB Output is correct
35 Correct 1233 ms 67424 KB Output is correct
36 Correct 1192 ms 67436 KB Output is correct
37 Correct 439 ms 79136 KB Output is correct
38 Correct 231 ms 69208 KB Output is correct
39 Correct 980 ms 76664 KB Output is correct
40 Correct 933 ms 76548 KB Output is correct
41 Correct 12 ms 23892 KB Output is correct
42 Correct 1222 ms 76940 KB Output is correct
43 Correct 687 ms 72708 KB Output is correct
44 Correct 770 ms 74812 KB Output is correct
45 Correct 1228 ms 70524 KB Output is correct
46 Correct 2337 ms 282884 KB Output is correct
47 Correct 1191 ms 237424 KB Output is correct
48 Correct 5267 ms 269448 KB Output is correct
49 Correct 5028 ms 269540 KB Output is correct
50 Correct 8135 ms 271464 KB Output is correct
51 Correct 4167 ms 249364 KB Output is correct
52 Correct 4354 ms 254696 KB Output is correct
53 Correct 7741 ms 239852 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 63032 KB Output is correct
2 Correct 655 ms 76644 KB Output is correct
3 Correct 177 ms 69192 KB Output is correct
4 Correct 526 ms 74324 KB Output is correct
5 Correct 13 ms 23892 KB Output is correct
6 Correct 711 ms 75268 KB Output is correct
7 Correct 70 ms 38568 KB Output is correct
8 Correct 74 ms 54976 KB Output is correct
9 Correct 185 ms 70360 KB Output is correct
10 Correct 893 ms 72888 KB Output is correct
11 Correct 147 ms 63688 KB Output is correct
12 Correct 13 ms 23816 KB Output is correct
13 Correct 12 ms 23892 KB Output is correct
14 Correct 12 ms 23832 KB Output is correct
15 Correct 13 ms 23840 KB Output is correct
16 Correct 12 ms 23892 KB Output is correct
17 Correct 13 ms 23888 KB Output is correct
18 Correct 12 ms 23936 KB Output is correct
19 Correct 14 ms 23832 KB Output is correct
20 Correct 12 ms 23864 KB Output is correct
21 Correct 12 ms 23948 KB Output is correct
22 Correct 12 ms 23892 KB Output is correct
23 Correct 12 ms 23892 KB Output is correct
24 Correct 12 ms 23892 KB Output is correct
25 Correct 12 ms 23892 KB Output is correct
26 Correct 12 ms 23832 KB Output is correct
27 Correct 12 ms 23876 KB Output is correct
28 Correct 14 ms 24360 KB Output is correct
29 Correct 13 ms 24324 KB Output is correct
30 Correct 19 ms 24404 KB Output is correct
31 Correct 16 ms 24348 KB Output is correct
32 Correct 16 ms 24356 KB Output is correct
33 Correct 19 ms 24336 KB Output is correct
34 Correct 18 ms 24276 KB Output is correct
35 Correct 349 ms 70584 KB Output is correct
36 Correct 203 ms 65980 KB Output is correct
37 Correct 375 ms 76184 KB Output is correct
38 Correct 213 ms 66164 KB Output is correct
39 Correct 442 ms 69000 KB Output is correct
40 Correct 167 ms 67168 KB Output is correct
41 Correct 1201 ms 73828 KB Output is correct
42 Correct 64 ms 36940 KB Output is correct
43 Correct 172 ms 55300 KB Output is correct
44 Correct 665 ms 69796 KB Output is correct
45 Correct 742 ms 71988 KB Output is correct
46 Correct 1233 ms 67424 KB Output is correct
47 Correct 1192 ms 67436 KB Output is correct
48 Correct 439 ms 79136 KB Output is correct
49 Correct 231 ms 69208 KB Output is correct
50 Correct 980 ms 76664 KB Output is correct
51 Correct 933 ms 76548 KB Output is correct
52 Correct 12 ms 23892 KB Output is correct
53 Correct 1222 ms 76940 KB Output is correct
54 Correct 687 ms 72708 KB Output is correct
55 Correct 770 ms 74812 KB Output is correct
56 Correct 1228 ms 70524 KB Output is correct
57 Incorrect 377 ms 79756 KB Output isn't correct
58 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 63032 KB Output is correct
2 Correct 655 ms 76644 KB Output is correct
3 Correct 177 ms 69192 KB Output is correct
4 Correct 526 ms 74324 KB Output is correct
5 Correct 13 ms 23892 KB Output is correct
6 Correct 711 ms 75268 KB Output is correct
7 Correct 70 ms 38568 KB Output is correct
8 Correct 74 ms 54976 KB Output is correct
9 Correct 185 ms 70360 KB Output is correct
10 Correct 893 ms 72888 KB Output is correct
11 Correct 147 ms 63688 KB Output is correct
12 Correct 13 ms 23816 KB Output is correct
13 Correct 12 ms 23892 KB Output is correct
14 Correct 12 ms 23832 KB Output is correct
15 Correct 13 ms 23840 KB Output is correct
16 Correct 12 ms 23892 KB Output is correct
17 Correct 13 ms 23888 KB Output is correct
18 Correct 12 ms 23936 KB Output is correct
19 Correct 14 ms 23832 KB Output is correct
20 Correct 12 ms 23864 KB Output is correct
21 Correct 12 ms 23948 KB Output is correct
22 Correct 12 ms 23892 KB Output is correct
23 Correct 12 ms 23892 KB Output is correct
24 Correct 12 ms 23892 KB Output is correct
25 Correct 12 ms 23892 KB Output is correct
26 Correct 12 ms 23832 KB Output is correct
27 Correct 12 ms 23876 KB Output is correct
28 Correct 14 ms 24360 KB Output is correct
29 Correct 13 ms 24324 KB Output is correct
30 Correct 19 ms 24404 KB Output is correct
31 Correct 16 ms 24348 KB Output is correct
32 Correct 16 ms 24356 KB Output is correct
33 Correct 19 ms 24336 KB Output is correct
34 Correct 18 ms 24276 KB Output is correct
35 Correct 349 ms 70584 KB Output is correct
36 Correct 203 ms 65980 KB Output is correct
37 Correct 375 ms 76184 KB Output is correct
38 Correct 213 ms 66164 KB Output is correct
39 Correct 442 ms 69000 KB Output is correct
40 Correct 167 ms 67168 KB Output is correct
41 Correct 1201 ms 73828 KB Output is correct
42 Correct 64 ms 36940 KB Output is correct
43 Correct 172 ms 55300 KB Output is correct
44 Correct 665 ms 69796 KB Output is correct
45 Correct 742 ms 71988 KB Output is correct
46 Correct 1233 ms 67424 KB Output is correct
47 Correct 1192 ms 67436 KB Output is correct
48 Correct 439 ms 79136 KB Output is correct
49 Correct 231 ms 69208 KB Output is correct
50 Correct 980 ms 76664 KB Output is correct
51 Correct 933 ms 76548 KB Output is correct
52 Correct 12 ms 23892 KB Output is correct
53 Correct 1222 ms 76940 KB Output is correct
54 Correct 687 ms 72708 KB Output is correct
55 Correct 770 ms 74812 KB Output is correct
56 Correct 1228 ms 70524 KB Output is correct
57 Correct 2337 ms 282884 KB Output is correct
58 Correct 1191 ms 237424 KB Output is correct
59 Correct 5267 ms 269448 KB Output is correct
60 Correct 5028 ms 269540 KB Output is correct
61 Correct 8135 ms 271464 KB Output is correct
62 Correct 4167 ms 249364 KB Output is correct
63 Correct 4354 ms 254696 KB Output is correct
64 Correct 7741 ms 239852 KB Output is correct
65 Incorrect 377 ms 79756 KB Output isn't correct
66 Halted 0 ms 0 KB -